<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Community
"Where do I belong?"
Definition of Community and Community Detection
Update NetworkX
Girvan-Newman Community Detection
K-Cliques Community Detection
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
Step2:  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
Step3:  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.
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).
Step4:  Karate Club Time
Step5:  Validation
<ASSISTANT_TASK:>
Python 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')
Explanation: Community
"Where do I belong?"
Definition of Community and Community Detection
Update NetworkX
Girvan-Newman Community Detection
K-Cliques Community Detection
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
End of explanation
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)
Explanation: 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.
End of explanation
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))
Explanation: 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.
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).
End of explanation
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)
Explanation: Karate Club Time
End of explanation
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'])
Explanation: Validation
End of explanation
<END_TASK>