<jupyter_start><jupyter_text>Community "Where do I belong?"- Definition of Community and Community Detection- Update NetworkX- Girvan-Newman Community Detection- K-Cliques Community Detection ![communities](https://upload.wikimedia.org/wikipedia/commons/thumb/f/f4/Network_Community_Structure.svg/200px-Network_Community_Structure.svg.png) Definitions__Communities__ (also called partitions, clusters, groupings) in networks are sets of nodes that are more densely connected within a community than between other communities. __Community detection__ aims to reveal underlying community structure and can be handled in several different ways.  Get the `2.0dev` version of Networkx```$ pip install git+https://github.com/networkx/networkx.git```*to undo:*```$ conda env update environment.yml```<jupyter_code>%reload_ext watermark
%watermark -p networkx
import networkx as nx
from networkx.algorithms.community import k_clique_communities, girvan_newman

import matplotlib.pyplot as plt
%matplotlib inline
GA = nx.read_gexf('../data/ga_graph.gexf')<jupyter_output><empty_output><jupyter_text>Girvan Newman Algorithm> The Girvan–Newman algorithm detects communities by progressively removing edges from the original graph. The algorithm removes the “most valuable” edge, traditionally the edge with the highest betweenness centrality, at each step. As the graph breaks down into pieces, the tightly knit community structure is exposed.NetworkX's `girvan_newman` __returns__:  ```Iterator over tuples of sets of nodes in G. Each set of nodes is a community, each tuple is a sequence of communities at a particular level of the algorithm.```<jupyter_code>gn_comm = girvan_newman(GA)
first_iteration_comm = tuple(sorted(c) for c in next(gn_comm))
dict(enumerate(first_iteration_comm))
def map_communities(G, communities):
    """Return a mapping of community membership from a community set tuple"""
    community_map = {}
    for node in G.nodes():
        for i, comm in enumerate(communities):
            if node in comm:
                community_map[node] = i
        if community_map.get(node, None) is None:
            community_map[node] = None
    return community_map
from helpers import create_color_map
community_map = map_communities(GA, first_iteration_comm)

nx.set_node_attributes(GA, 'community', community_map)

node_colors, color_map, palette = create_color_map(GA, 'community')
nx.draw(GA, node_color=node_colors, with_labels=True)
second_comm = tuple(sorted(c) for c in next(gn_comm))

community_map_2 = map_communities(GA, second_comm)

nx.set_node_attributes(GA, 'community two', community_map_2)

node_colors, color_map, palette = create_color_map(GA, 'community two')
nx.draw(GA, node_color=node_colors, with_labels=True)<jupyter_output><empty_output><jupyter_text>K-Clique Communities> a __clique__ is a subset of vertices of an undirected graph such that its induced subgraph is complete; that is, every two distinct vertices in the clique are adjacent. > A __k-clique community__ is the union of all cliques of size k that can be reached through adjacent (sharing k-1 nodes) k-cliques. ![cliques](https://upload.wikimedia.org/wikipedia/commons/thumb/d/d0/VR_complex.svg/500px-VR_complex.svg.png)A graph with- 23 × 1-vertex cliques (the vertices),- 42 × 2-vertex cliques (the edges),- 19 × 3-vertex cliques (light and dark blue triangles), and- 2 × 4-vertex cliques (dark blue areas).<jupyter_code>k_clique = k_clique_communities(GA, 2)
dict(enumerate(k_clique))
k_clique = k_clique_communities(GA, 3)
dict(enumerate(k_clique))
print("Percent of ALL edges that could exist: %0.2f" % (nx.density(GA) * 100))<jupyter_output>Percent of ALL edges that could exist: 6.85<jupyter_text>Karate Club Time!["kicking butt"](http://andover-karate-club.co.uk/wp-content/uploads/2014/02/karateleader.png)<jupyter_code>Karate = nx.karate_club_graph()
gn_comm = girvan_newman(Karate)

first_comm = tuple(sorted(c) for c in next(gn_comm))

community_map = map_communities(Karate, first_comm)

nx.set_node_attributes(Karate, 'community gn', community_map)

node_colors, color_map, palette = create_color_map(Karate, 'community gn')
nx.draw(Karate, node_color=node_colors, with_labels=True)
k_clique = k_clique_communities(Karate, 3)

k_clique_comm = [list(community) for community in k_clique]

community_map = map_communities(Karate, k_clique_comm)

nx.set_node_attributes(Karate, 'community k-clique', community_map)

node_colors, color_map, palette = create_color_map(Karate, 'community k-clique')
nx.draw(Karate, node_color=node_colors, with_labels=True)<jupyter_output><empty_output><jupyter_text>Validation<jupyter_code>import pandas as pd
club_community = [Karate.node[node] for node in Karate.nodes()]

club_df = pd.DataFrame(club_community)
pd.crosstab(club_df['club'], club_df['community gn'])
pd.crosstab(club_df['club'], club_df['community k-clique'])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09759085340955492, 'fraction_numerical': 0.008370763576970192, 'mean_word_length': 6.344827586206897, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 23, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '290763', 'license': 'MIT', 'n_tokens_mistral': 1640, 'n_tokens_neox': 1540, 'n_words': 439, 'path': 'notebooks/6. Community.ipynb', 'repo_name': 'maximusKarlson/networkx', 'size': '4898'}