ioftools / networkxMiCe / networkxmaster / networkx / algorithms / hierarchy.py @ 5cef0f13
History  View  Annotate  Download (1.74 KB)
1 
# * coding: utf8 *


2 
"""

3 
Flow Hierarchy.

4 
"""

5 
# Copyright (C) 20042019 by

6 
# Aric Hagberg <hagberg@lanl.gov>

7 
# Dan Schult <dschult@colgate.edu>

8 
# Pieter Swart <swart@lanl.gov>

9 
# All rights reserved.

10 
# BSD license.

11 
import networkx as nx 
12 
__authors__ = "\n".join(['Ben Edwards (bedwards@cs.unm.edu)']) 
13 
__all__ = ['flow_hierarchy']

14  
15  
16 
def flow_hierarchy(G, weight=None): 
17 
"""Returns the flow hierarchy of a directed network.

18 

19 
Flow hierarchy is defined as the fraction of edges not participating

20 
in cycles in a directed graph [1]_.

21 

22 
Parameters

23 


24 
G : DiGraph or MultiDiGraph

25 
A directed graph

26 

27 
weight : key,optional (default=None)

28 
Attribute to use for node weights. If None the weight defaults to 1.

29 

30 
Returns

31 


32 
h : float

33 
Flow hierarchy value

34 

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.

42 

43 
References

44 


45 
.. [1] Luo, J.; Magee, C.L. (2011),

46 
Detecting evolving patterns of selforganizing networks by flow

47 
hierarchy measurement, Complexity, Volume 16 Issue 6 5361.

48 
DOI: 10.1002/cplx.20368

49 
http://web.mit.edu/~cmagee/www/documents/28DetectingEvolvingPatterns_FlowHierarchy.pdf

50 
"""

51 
if not G.is_directed(): 
52 
raise nx.NetworkXError("G must be a digraph in flow_heirarchy") 
53 
scc = nx.strongly_connected_components(G) 
54 
return 1.  sum(G.subgraph(c).size(weight) for c in scc) / float(G.size(weight)) 