This module implements community detection.
Return the partition of the nodes at the given level
A dendogram is a tree and each level is a partition of the graph nodes. Level 0 is the first partition, which contains the smallest communities, and the best is len(dendogram) - 1. The higher the level is, the bigger are the communities
| Parameters : | dendogram : list of dict
level : int
|
|---|---|
| Returns : | partition : dictionnary
|
| Raises : | KeyError :
|
See also
Examples
>>> G=nx.erdos_renyi_graph(100, 0.01)
>>> dendo = generate_dendogram(G)
>>> for level in range(len(dendo) - 1) :
>>> print "partition at level", level, "is", partition_at_level(dendo, level)
Compute the modularity of a partition of a graph
| Parameters : | partition : dict
graph : networkx.Graph
|
|---|---|
| Returns : | modularity : float
|
| Raises : | KeyError :
ValueError :
TypeError :
|
References
Examples
>>> G=nx.erdos_renyi_graph(100, 0.01)
>>> part = best_partition(G)
>>> modularity(part, G)
Compute the partition of the graph nodes which maximises the modularity (or try..) using the Louvain heuristices
This is the partition of highest modularity, i.e. the highest partition of the dendogram generated by the Louvain algorithm.
| Parameters : | graph : networkx.Graph
partition : dict, optionnal
|
|---|---|
| Returns : | partition : dictionnary
|
| Raises : | NetworkXError :
|
See also
Notes
Uses Louvain algorithm
References
Examples
>>> #Basic usage
>>> G=nx.erdos_renyi_graph(100, 0.01)
>>> part = best_partition(G)
>>> #other example to display a graph with its community :
>>> #better with karate_graph() as defined in networkx examples
>>> #erdos renyi don't have true community structure
>>> G = nx.erdos_renyi_graph(30, 0.05)
>>> #first compute the best partition
>>> partition = community.best_partition(G)
>>> #drawing
>>> size = float(len(set(partition.values())))
>>> pos = nx.spring_layout(G)
>>> count = 0.
>>> for com in set(partition.values()) :
>>> count = count + 1.
>>> list_nodes = [nodes for nodes in partition.keys()
>>> if partition[nodes] == com]
>>> nx.draw_networkx_nodes(G, pos, list_nodes, node_size = 20,
node_color = str(count / size))
>>> nx.draw_networkx_edges(G,pos, alpha=0.5)
>>> plt.show()
Find communities in the graph and return the associated dendogram
A dendogram is a tree and each level is a partition of the graph nodes. Level 0 is the first partition, which contains the smallest communities, and the best is len(dendogram) - 1. The higher the level is, the bigger are the communities
| Parameters : | graph : networkx.Graph
part_init : dict, optionnal
|
|---|---|
| Returns : | dendogram : list of dictionaries
|
| Raises : | TypeError :
|
See also
Notes
Uses Louvain algorithm
References
Examples
>>> G=nx.erdos_renyi_graph(100, 0.01)
>>> dendo = generate_dendogram(G)
>>> for level in range(len(dendo) - 1) :
>>> print "partition at level", level, "is", partition_at_level(dendo, level)
Produce the graph where nodes are the communities
there is a link of weight w between communities if the sum of the weights of the links between their elements is w
| Parameters : | partition : dict
graph : networkx.Graph
|
|---|---|
| Returns : | g : networkx.Graph
|
Examples
>>> n = 5
>>> g = nx.complete_graph(2*n)
>>> part = dict([])
>>> for node in g.nodes() :
>>> part[node] = node % 2
>>> ind = induced_graph(part, g)
>>> goal = nx.Graph()
>>> goal.add_weighted_edges_from([(0,1,n*n),(0,0,n*(n-1)/2), (1, 1, n*(n-1)/2)])
>>> nx.is_isomorphic(int, goal)
True