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


2 
"""

3 
Spectral bipartivity measure.

4 
"""

5 
import networkx as nx 
6 
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""

7 
# Copyright (C) 2011 by

8 
# Aric Hagberg <hagberg@lanl.gov>

9 
# Dan Schult <dschult@colgate.edu>

10 
# Pieter Swart <swart@lanl.gov>

11 
# All rights reserved.

12 
# BSD license.

13 
__all__ = ['spectral_bipartivity']

14  
15  
16 
def spectral_bipartivity(G, nodes=None, weight='weight'): 
17 
"""Returns the spectral bipartivity.

18 

19 
Parameters

20 


21 
G : NetworkX graph

22 

23 
nodes : list or container optional(default is all nodes)

24 
Nodes to return value of spectral bipartivity contribution.

25 

26 
weight : string or None optional (default = 'weight')

27 
Edge data key to use for edge weights. If None, weights set to 1.

28 

29 
Returns

30 


31 
sb : float or dict

32 
A single number if the keyword nodes is not specified, or

33 
a dictionary keyed by node with the spectral bipartivity contribution

34 
of that node as the value.

35 

36 
Examples

37 


38 
>>> from networkx.algorithms import bipartite

39 
>>> G = nx.path_graph(4)

40 
>>> bipartite.spectral_bipartivity(G)

41 
1.0

42 

43 
Notes

44 


45 
This implementation uses Numpy (dense) matrices which are not efficient

46 
for storing large sparse graphs.

47 

48 
See Also

49 


50 
color

51 

52 
References

53 


54 
.. [1] E. Estrada and J. A. RodríguezVelázquez, "Spectral measures of

55 
bipartivity in complex networks", PhysRev E 72, 046105 (2005)

56 
"""

57 
try:

58 
import scipy.linalg 
59 
except ImportError: 
60 
raise ImportError('spectral_bipartivity() requires SciPy: ', 
61 
'http://scipy.org/')

62 
nodelist = list(G) # ordering of nodes in matrix 
63 
A = nx.to_numpy_matrix(G, nodelist, weight=weight) 
64 
expA = scipy.linalg.expm(A) 
65 
expmA = scipy.linalg.expm(A) 
66 
coshA = 0.5 * (expA + expmA)

67 
if nodes is None: 
68 
# return single number for entire graph

69 
return coshA.diagonal().sum() / expA.diagonal().sum()

70 
else:

71 
# contribution for individual nodes

72 
index = dict(zip(nodelist, range(len(nodelist)))) 
73 
sb = {} 
74 
for n in nodes: 
75 
i = index[n] 
76 
sb[n] = coshA[i, i] / expA[i, i] 
77 
return sb

78  
79  
80 
def setup_module(module): 
81 
"""Fixture for nose tests."""

82 
from nose import SkipTest 
83 
try:

84 
import numpy 
85 
except:

86 
raise SkipTest("NumPy not available") 
87 
try:

88 
import scipy 
89 
except:

90 
raise SkipTest("SciPy not available") 