Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Flow Hierarchy.
3"""
5import networkx as nx
7__all__ = ["flow_hierarchy"]
10@nx._dispatchable(edge_attrs="weight")
11def flow_hierarchy(G, weight=None):
12 """Returns the flow hierarchy of a directed network.
14 Flow hierarchy is defined as the fraction of edges not participating
15 in cycles in a directed graph [1]_.
17 Parameters
18 ----------
19 G : DiGraph or MultiDiGraph
20 A directed graph
22 weight : string, optional (default=None)
23 Attribute to use for edge weights. If None the weight defaults to 1.
25 Returns
26 -------
27 h : float
28 Flow hierarchy value
30 Raises
31 ------
32 NetworkXError
33 If `G` is not a directed graph or if `G` has no edges.
35 Notes
36 -----
37 The algorithm described in [1]_ computes the flow hierarchy through
38 exponentiation of the adjacency matrix. This function implements an
39 alternative approach that finds strongly connected components.
40 An edge is in a cycle if and only if it is in a strongly connected
41 component, which can be found in $O(m)$ time using Tarjan's algorithm.
43 References
44 ----------
45 .. [1] Luo, J.; Magee, C.L. (2011),
46 Detecting evolving patterns of self-organizing networks by flow
47 hierarchy measurement, Complexity, Volume 16 Issue 6 53-61.
48 DOI: 10.1002/cplx.20368
49 http://web.mit.edu/~cmagee/www/documents/28-DetectingEvolvingPatterns_FlowHierarchy.pdf
50 """
51 # corner case: G has no edges
52 if nx.is_empty(G):
53 raise nx.NetworkXError("flow_hierarchy not applicable to empty graphs")
54 if not G.is_directed():
55 raise nx.NetworkXError("G must be a digraph in flow_hierarchy")
56 scc = nx.strongly_connected_components(G)
57 return 1 - sum(G.subgraph(c).size(weight) for c in scc) / G.size(weight)