def calculate_katz_centrality(graph):
"""
Compute the katz centrality for nodes.
"""
# if not graph.is_directed():
# raise nx.NetworkXError( \
# "katz_centrality() not defined for undirected graphs.")
print "\n\tCalculating Katz Centrality..."
print "\tWarning: This might take a long time larger pedigrees."
g = graph
A = nx.adjacency_matrix(g)
from scipy import linalg as LA
max_eign = float(np.real(max(LA.eigvals(A.todense()))))
print "\t-Max.Eigenvalue(A) ", round(max_eign, 3)
kt = nx.katz_centrality(g, tol=1.0e-4, alpha=1/max_eign-0.01, beta=1.0, max_iter=999999)
nx.set_node_attributes(g, 'katz', kt)
katz_sorted = sorted(kt.items(), key=itemgetter(1), reverse=True)
for key, value in katz_sorted[0:10]:
print "\t > ", key, round(value, 4)
return g, kt
python类NetworkXError()的实例源码
def ordered_neighbors(nx_graph, our_address, target_address):
paths = list()
try:
all_neighbors = networkx.all_neighbors(nx_graph, our_address)
except networkx.NetworkXError:
# If `our_address` is not in the graph, no channels opened with the
# address
return []
for neighbor in all_neighbors:
try:
length = networkx.shortest_path_length(
nx_graph,
neighbor,
target_address,
)
heappush(paths, (length, neighbor))
except (networkx.NetworkXNoPath, networkx.NodeNotFound):
pass
return paths
def __init__(self, data=None, **attr):
self.node_dict_factory = ndf = self.node_dict_factory
self.adjlist_dict_factory = self.adjlist_dict_factory
self.edge_attr_dict_factory = self.edge_attr_dict_factory
self.graph = {} # dictionary for graph attributes
self.node = ndf() # empty node attribute dict
self.adj = ndf() # empty adjacency dict
# attempt to load graph with data
if data is not None:
if isinstance(data, OrderedGraph):
try:
nx.convert.from_dict_of_dicts(
data.adj,
create_using=self,
multigraph_input=data.is_multigraph()
)
self.graph = data.graph.copy()
self.node.update((n,d.copy()) for n,d in data.node.items())
except:
raise nx.NetworkXError("Input is not a correct NetworkX graph.")
else:
nx.convert.to_networkx_graph(data, create_using=self)
def projected_graph(B, nodes, multigraph=False):
if B.is_multigraph():
raise nx.NetworkXError("not defined for multigraphs")
if B.is_directed():
directed=True
if multigraph:
G=nx.MultiDiGraph()
else:
G=nx.DiGraph()
else:
directed=False
if multigraph:
G=nx.MultiGraph()
else:
G=nx.Graph()
G.graph.update(B.graph)
G.add_nodes_from((n,B.node[n]) for n in nodes)
i = 0
nodes = set(nodes)
tenpercent = len(nodes) / 10
for u in nodes:
if i % tenpercent == 0:
logging.info(str(10 * i / tenpercent) + "%")
i += 1
nbrs2=set((v for nbr in B[u] for v in B[nbr])) & nodes - set([u])
if multigraph:
for n in nbrs2:
if directed:
links=set(B[u]) & set(B.pred[n])
else:
links=set(B[u]) & set(B[n])
for l in links:
if not G.has_edge(u,n,l):
G.add_edge(u,n,key=l)
else:
G.add_edges_from((u,n) for n in nbrs2)
return G
def collaboration_weighted_projected_graph(B, nodes):
if B.is_multigraph():
raise nx.NetworkXError("not defined for multigraphs")
if B.is_directed():
pred=B.pred
G=nx.DiGraph()
else:
pred=B.adj
G=nx.Graph()
G.graph.update(B.graph)
G.add_nodes_from((n,B.node[n]) for n in nodes)
i = 0
nodes = set(nodes)
tenpercent = len(nodes) / 10
for u in nodes:
if i % tenpercent == 0:
logging.info(str(10 * i / tenpercent) + "%")
i += 1
unbrs = set(B[u])
nbrs2 = set((n for nbr in unbrs for n in B[nbr])) & nodes - set([u])
for v in nbrs2:
vnbrs = set(pred[v])
common = unbrs & vnbrs
weight = sum([1.0/(len(B[n]) - 1) for n in common if len(B[n])>1])
G.add_edge(u,v,w=weight)
return G
def out_degree_centrality(G):
"""Compute the out-degree centrality for nodes.
The out-degree centrality for a node v is the fraction of nodes its
outgoing edges are connected to.
Parameters
----------
G : graph
A NetworkX graph
Returns
-------
nodes : dictionary
Dictionary of nodes with out-degree centrality as values.
See Also
--------
degree_centrality, in_degree_centrality
Notes
-----
The degree centrality values are normalized by dividing by the maximum
possible degree in a simple graph n-1 where n is the number of nodes in G.
For multigraphs or graphs with self loops the maximum degree might
be higher than n-1 and values of degree centrality greater than 1
are possible.
"""
if not G.is_directed():
raise nx.NetworkXError( \
"out_degree_centrality() not defined for undirected graphs.")
centrality = {}
s = 1.0 / (len(G) - 1.0)
centrality = dict((n, d * s) for n, d in G.out_degree_iter())
return centrality
def get_neighbours(self):
""" Get all neihbours adjacent to self.our_address. """
try:
return networkx.all_neighbors(self.graph, self.our_address)
except networkx.NetworkXError:
return []
def get_measures(self):
if self.measure not in self.measures:
raise nx.NetworkXError('The measure is not appointed correct.')
for measure in self.measures:
get_measures = getattr(self, 'get_%ss' % measure)
ranks, max_rank = get_measures()
self.ranks[measure] = {'ranks': ranks, 'max': max_rank}
def add_edge(self, u, v, *args, **kwargs):
changed = False
if u == v:
if self.flags['strict']:
raise ValueError('Edge must be between two unique nodes!')
return changed
if self._undirected.has_edge(u, v):
self.remove_edges_from([[u, v], [v,u]])
elif len(self.nodes()) > 0:
try:
path = nx.shortest_path(self._undirected, u, v)
if self.flags['strict']:
raise ValueError('Multiple edge path exists between nodes!')
self.disconnect_path(path)
changed = True
except (nx.NetworkXError, nx.NetworkXNoPath):
pass
self._undirected.add_edge(u,v)
super(self.__class__, self).add_edge(u, v, *args, **kwargs)
if self.flags['assert_forest']:
# this is quite slow but makes very sure structure is correct
# so is mainly used for testing
assert nx.is_forest(nx.Graph(self))
return changed
def get_purge_list(self):
"""Returns a list of entitites that should be purged from the db"""
to_purge = set(self.missing)
graph = self._build_dependency_graph()
if not graph:
return to_purge
collected = set(entitykey(e) for e in self.get_managed())
missing = (miss for miss in self.missing
if miss.device is not None and miss in to_purge)
for miss in missing:
if miss not in graph:
self._logger.warning(
"missing entity cannot be found in dependency graph, maybe "
"the plugin that originally collected it didn't run? : "
"%r : %r", miss, graph.nodes())
continue
try:
sub = subtree(graph, miss)
except nx.NetworkXError as err:
self._logger.warning(
"Ignoring suspicious error during processing of entity "
"relationships in ENTITY-MIB::entPhysicalTable: %s", err)
continue
# filter away any missing entity whose index appears to have
# been re-used
not_replaced = [n for n in sub if entitykey(n) not in collected]
to_purge.difference_update(not_replaced)
return to_purge
def _all_simple_paths(G, source, target, cutoff=None):
"""
Adaptation of nx.all_simple_paths for mutligraphs
"""
if source not in G:
raise nx.NetworkXError('source node %s not in graph'%source)
if target not in G:
raise nx.NetworkXError('target node %s not in graph'%target)
if cutoff is None:
cutoff = len(G)-1
if G.is_multigraph():
return _all_simple_paths_multigraph(G, source, target, cutoff=cutoff)
else:
return 1 #_all_simple_paths_graph(G, source, target, cutoff=cutoff)
def update(self):
"""
Tells RideD to update itself by getting the latest subscribers, publishers,
publication routes, and topology. It rebuilds and reinstalls the multicast
trees if necessary.
:return:
"""
# ENHANCE: extend the REST APIs to support updating the topology rather than getting a whole new one.
self.topology_manager.build_topology(from_scratch=True)
# TODO: need to invalidate outstanding alerts if the MDMTs change! or at least invalidate their changed MDMTs...
# XXX: during lots of failures, the updated topology won't see a lot of the nodes so we'll be catching errors...
trees = None
try:
trees = self.build_mdmts()
# TODO: maybe we should only save the built MDMTs as we add their flow rules? this could ensure that any MDMT we try to use will at least be fully-installed...
# could even use a thread lock to block until the first one is installed
self.mdmts = trees
except nx.NetworkXError as e:
log.error("failed to create MDMTs (likely due to topology disconnect) due to error: \n%s" % e)
if trees:
# ENHANCE: error checking/handling esp. for the multicast address pool that must be shared across all topics!
for mdmts in trees.values():
try:
self.install_mdmts(mdmts)
except nx.NetworkXError as e:
log.error("failed to install_mdmts due to error: %s" % e)
elif self.subscribers:
log.error("empty return value from build_mdmts() when we do have subscribers!")
# ENHANCE: retrieve publication routes rather than rely on them being manually set...
