Community detection

Table Of Contents

Previous topic

Community detection for NetworkX’s documentation

This Page

community API

This module implements community detection.

community.partition_at_level(dendogram, level)

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

a list of partitions, ie dictionnaries where keys of the i+1 are the values of the i.

level : int

the level which belongs to [0..len(dendogram)-1]

Returns :

partition : dictionnary

A dictionary where keys are the nodes and the values are the set it belongs to

Raises :

KeyError :

If the dendogram is not well formed or the level is too high

See also

best_partition

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)
community.modularity(partition, graph)

Compute the modularity of a partition of a graph

Parameters :

partition : dict

the partition of the nodes, i.e a dictionary where keys are their nodes and values the communities

graph : networkx.Graph

the networkx graph which is decomposed

Returns :

modularity : float

The modularity

Raises :

KeyError :

If the partition is not a partition of all graph nodes

ValueError :

If the graph has no link

TypeError :

If graph is not a networkx.Graph

References

Examples

>>> G=nx.erdos_renyi_graph(100, 0.01)
>>> part = best_partition(G)
>>> modularity(part, G)
community.best_partition(graph, partition=None)

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

the networkx graph which is decomposed

partition : dict, optionnal

the algorithm will start using this partition of the nodes. It’s a dictionary where keys are their nodes and values the communities

Returns :

partition : dictionnary

The partition, with communities numbered from 0 to number of communities

Raises :

NetworkXError :

If the graph is not Eulerian.

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()
community.generate_dendogram(graph, part_init=None)

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

the networkx graph which will be decomposed

part_init : dict, optionnal

the algorithm will start using this partition of the nodes. It’s a dictionary where keys are their nodes and values the communities

Returns :

dendogram : list of dictionaries

a list of partitions, ie dictionnaries where keys of the i+1 are the values of the i. and where keys of the first are the nodes of graph

Raises :

TypeError :

If the graph is not a networkx.Graph

See also

best_partition

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)
community.induced_graph(partition, graph)

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

a dictionary where keys are graph nodes and values the part the node belongs to

graph : networkx.Graph

the initial graph

Returns :

g : networkx.Graph

a networkx graph where nodes are the parts

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

Indices and tables