### comparison env/lib/python3.9/site-packages/networkx/algorithms/hierarchy.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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))