py3plex.algorithms.community_detection.community package

Submodules

py3plex.algorithms.community_detection.community.community_louvain module

This module implements community detection.

class py3plex.algorithms.community_detection.community.community_louvain.Status

Bases: object

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

degrees = {}

gdegrees = {}

init(graph, weight, part=None)

Initialize the status of a graph with every node in one community

internals = {}

node2com = {}

total_weight = 0

py3plex.algorithms.community_detection.community.community_louvain.best_partition(graph, partition=None, weight='weight', resolution=1.0, randomize=False)

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 dendrogram generated by the Louvain algorithm.

Parameters

• graph (networkx.Graph) – the networkx graph which is decomposed

• partition (dict, optional) – the algorithm will start using this partition of the nodes. It’s a dictionary where keys are their nodes and values the communities

• weight (str, optional) – the key in graph to use as weight. Default to ‘weight’

• resolution (double, optional) – Will change the size of the communities, default to 1. represents the time described in “Laplacian Dynamics and Multiscale Modular Structure in Networks”, R. Lambiotte, J.-C. Delvenne, M. Barahona

• randomize (boolean, optional) – Will randomize the node evaluation order and the community evaluation order to get different partitions at each call

Returns

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

Return type

dictionnary

Raises

NetworkXError – If the graph is not Eulerian.

See also

generate_dendrogram()

Notes

Uses Louvain algorithm

References

large networks. J. Stat. Mech 10008, 1-12(2008).

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 += 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()

py3plex.algorithms.community_detection.community.community_louvain.generate_dendrogram(graph, part_init=None, weight='weight', resolution=1.0, randomize=False)

Find communities in the graph and return the associated dendrogram

A dendrogram 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(dendrogram) - 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, optional) – the algorithm will start using this partition of the nodes. It’s a dictionary where keys are their nodes and values the communities

• weight (str, optional) – the key in graph to use as weight. Default to ‘weight’

• resolution (double, optional) – Will change the size of the communities, default to 1. represents the time described in “Laplacian Dynamics and Multiscale Modular Structure in Networks”, R. Lambiotte, J.-C. Delvenne, M. Barahona

Returns

dendrogram – 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

Return type

list of dictionaries

Raises

TypeError – If the graph is not a networkx.Graph

See also

best_partition()

Notes

Uses Louvain algorithm

References

networks. J. Stat. Mech 10008, 1-12(2008).

Examples

>>> G=nx.erdos_renyi_graph(100, 0.01)
>>> dendo = generate_dendrogram(G)
>>> for level in range(len(dendo) - 1) :
>>>     print("partition at level", level,
>>>           "is", partition_at_level(dendo, level))
:param weight:
:type weight:

py3plex.algorithms.community_detection.community.community_louvain.induced_graph(partition, graph, weight='weight')

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

• weight (str, optional) – the key in graph to use as weight. Default to ‘weight’

Returns

g – a networkx graph where nodes are the parts

Return type

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)])  # NOQA
>>> nx.is_isomorphic(int, goal)
True

py3plex.algorithms.community_detection.community.community_louvain.load_binary(data)

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

py3plex.algorithms.community_detection.community.community_louvain.modularity(partition, graph, weight='weight')

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

• weight (str, optional) – the key in graph to use as weight. Default to ‘weight’

Returns

modularity – The modularity

Return type

float

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

structure in networks. Physical Review E 69, 26113(2004).

Examples

>>> G=nx.erdos_renyi_graph(100, 0.01)
>>> part = best_partition(G)
>>> modularity(part, G)

py3plex.algorithms.community_detection.community.community_louvain.partition_at_level(dendrogram, level)

Return the partition of the nodes at the given level

A dendrogram 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(dendrogram) - 1. The higher the level is, the bigger are the communities

Parameters

• dendrogram (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(dendrogram)-1]

Returns

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

Return type

dictionnary

Raises

KeyError – If the dendrogram is not well formed or the level is too high

See also

best_partition(), generate_dendrogram()

Examples

>>> G=nx.erdos_renyi_graph(100, 0.01)
>>> dendrogram = generate_dendrogram(G)
>>> for level in range(len(dendrogram) - 1) :
>>>     print("partition at level", level, "is", partition_at_level(dendrogram, level))  # NOQA

py3plex.algorithms.community_detection.community.community_status module

class py3plex.algorithms.community_detection.community.community_status.Status

Bases: object

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

degrees = {}

gdegrees = {}

init(graph, weight, part=None)

Initialize the status of a graph with every node in one community

internals = {}

node2com = {}

total_weight = 0

Module contents

This package implements community detection.

Package name is community but refer to python-louvain on pypi