Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/hierarchy.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Flow Hierarchy. | |
3 """ | |
4 import networkx as nx | |
5 | |
6 __all__ = ["flow_hierarchy"] | |
7 | |
8 | |
9 def flow_hierarchy(G, weight=None): | |
10 """Returns the flow hierarchy of a directed network. | |
11 | |
12 Flow hierarchy is defined as the fraction of edges not participating | |
13 in cycles in a directed graph [1]_. | |
14 | |
15 Parameters | |
16 ---------- | |
17 G : DiGraph or MultiDiGraph | |
18 A directed graph | |
19 | |
20 weight : key,optional (default=None) | |
21 Attribute to use for node weights. If None the weight defaults to 1. | |
22 | |
23 Returns | |
24 ------- | |
25 h : float | |
26 Flow hierarchy value | |
27 | |
28 Notes | |
29 ----- | |
30 The algorithm described in [1]_ computes the flow hierarchy through | |
31 exponentiation of the adjacency matrix. This function implements an | |
32 alternative approach that finds strongly connected components. | |
33 An edge is in a cycle if and only if it is in a strongly connected | |
34 component, which can be found in $O(m)$ time using Tarjan's algorithm. | |
35 | |
36 References | |
37 ---------- | |
38 .. [1] Luo, J.; Magee, C.L. (2011), | |
39 Detecting evolving patterns of self-organizing networks by flow | |
40 hierarchy measurement, Complexity, Volume 16 Issue 6 53-61. | |
41 DOI: 10.1002/cplx.20368 | |
42 http://web.mit.edu/~cmagee/www/documents/28-DetectingEvolvingPatterns_FlowHierarchy.pdf | |
43 """ | |
44 if not G.is_directed(): | |
45 raise nx.NetworkXError("G must be a digraph in flow_hierarchy") | |
46 scc = nx.strongly_connected_components(G) | |
47 return 1.0 - sum(G.subgraph(c).size(weight) for c in scc) / float(G.size(weight)) |