Community detection

Table Of Contents

Previous topic

Community detection for NetworkX’s documentation

This Page

community API

This module implements community detection.

class community.Status

To handle several data in one struct.

Could be replaced by named tuple, but don’t want to depend on python 2.6

copy()
Perform a deep copy of status
init(graph, part=None)
Initialize the status of a graph with every node in one community
community.best_partition(graph, partition=None)

Compute the partition of the graph nodes which maximises the modularity (or try..) using the Louvain heuristices

Parameters:
  • graph (networkx graph) – the networkx graph which is decomposed
  • partition (dictionary, optional) – the algorithm will start using this partition of the nodes. It’s a dictionary where keys are their nodes and values the communities
Return type:

dictionary

Returns:

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

community.generate_dendogram(graph, part_init=None)

Find communities in the graph and return the associated dendogram

Parameters:
  • graph (networkx graph) – the networkx graph which will be decomposed
  • part_init (dictionary, optional) – the algorithm will start using this partition of the nodes. It’s a dictionary where keys are their nodes and values the communities
Return type:

list of dictionaries

Returns:

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

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 (dictionary) – a dictionary where keys are graph nodes and values the part the node belongs to
  • graph (networkx graph) – the initial graph
Return type:

networkx.Graph

Returns:

a networkx graph where nodes are the parts

community.load_binary(data)

Load binary graph as used by the cpp implementation of this algorithm

Parameter:data (string or file) – the file containing the data
Return type:networkx.Graph
Returns:The graph
community.modularity(partition, graph)

Compute the modularity of a partition of a graph

Parameters:
  • partition (dictionary) – 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
Return type:

float

Returns:

The modularity

community.one_level(graph, status)

Compute one level of communities

Parameters:
  • graph (dictionary) – the graph we are working on
  • status (Status) – a named tuple with node2com, total_weight, internals, degrees set
Returns:

nothing, the status is modified during the function

community.partition_at_level(dendogram, level)

Return the partition of the nodes at the given level

Level 0 is the first partition, and the best is len(dendogram) - 1

Parameters:
  • dendogram (list of dictionary) – a list of partitions, ie dictionnaries where keys of the i+1 are the values of the i.
  • level (integer) – an integer which belongs to [0..len(dendogram)-1]
Return type:

dictionary

Returns:

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

community.renumber(dictionary)

Renumber the values of the dictionary from 0 to n

Parameter:dictionary (dictionary) – the partition
Return type:dictionary
Returns:The modified partition

Indices and tables