py3plex.algorithms.community_detection package¶
Subpackages¶
Submodules¶
py3plex.algorithms.community_detection.NoRC module¶
-
py3plex.algorithms.community_detection.NoRC.
NoRC_communities_main
(input_graph, clustering_scheme='hierarchical', max_com_num=100, verbose=False, sparisfy=True, parallel_step=6, prob_threshold=0.0005, community_range=[1, 3, 5, 7, 11, 20, 40, 50, 100, 200, 300], fine_range=3, lag_threshold=10)¶
-
py3plex.algorithms.community_detection.NoRC.
create_tree
(centers)¶
-
py3plex.algorithms.community_detection.NoRC.
page_rank_kernel
(index_row)¶
-
py3plex.algorithms.community_detection.NoRC.
sum
(X, v)¶
py3plex.algorithms.community_detection.community_louvain module¶
This module implements community detection.
-
class
py3plex.algorithms.community_detection.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_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
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_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
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_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_louvain.
load_binary
(data)¶ Load binary graph as used by the cpp implementation of this algorithm
-
py3plex.algorithms.community_detection.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_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
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_measures module¶
-
py3plex.algorithms.community_detection.community_measures.
modularity
(G, communities, weight='weight')¶
-
py3plex.algorithms.community_detection.community_measures.
number_of_communities
(network_partition)¶
-
py3plex.algorithms.community_detection.community_measures.
size_distribution
(network_partition)¶
py3plex.algorithms.community_detection.community_ranking module¶
py3plex.algorithms.community_detection.community_wrapper module¶
-
py3plex.algorithms.community_detection.community_wrapper.
NoRC_communities
(network, verbose=True, clustering_scheme='kmeans', output='mapping', prob_threshold=0.001, parallel_step=8, community_range=[1, 3, 5, 7, 11, 20, 40, 50, 100, 200, 300], fine_range=3)¶
-
py3plex.algorithms.community_detection.community_wrapper.
infomap_communities
(graph, binary='./infomap', edgelist_file='./tmp/tmpedgelist.txt', multiplex=False, verbose=False, overlapping=False, iterations=200, output='mapping')¶
-
py3plex.algorithms.community_detection.community_wrapper.
louvain_communities
(network, output='mapping')¶
-
py3plex.algorithms.community_detection.community_wrapper.
parse_infomap
(outfile)¶
-
py3plex.algorithms.community_detection.community_wrapper.
run_infomap
(infile, multiplex=True, overlapping=False, binary='./infomap', verbose=True, iterations=1000)¶
py3plex.algorithms.community_detection.node_ranking module¶
-
py3plex.algorithms.community_detection.node_ranking.
hub_matrix
(graph)¶
-
py3plex.algorithms.community_detection.node_ranking.
modularity
(G, communities, weight='weight')¶
-
py3plex.algorithms.community_detection.node_ranking.
page_rank_kernel
(index_row)¶
-
py3plex.algorithms.community_detection.node_ranking.
sparse_page_rank
(matrix, start_nodes, epsilon=1e-06, max_steps=100000, damping=0.5, spread_step=10, spread_percent=0.3, try_shrink=False)¶
-
py3plex.algorithms.community_detection.node_ranking.
stochastic_normalization
(matrix)¶
-
py3plex.algorithms.community_detection.node_ranking.
stochastic_normalization_hin
(matrix)¶