diff options
Diffstat (limited to 'lib/python2.7/site-packages/setoolsgui/networkx/algorithms/core.py')
| -rw-r--r-- | lib/python2.7/site-packages/setoolsgui/networkx/algorithms/core.py | 324 |
1 files changed, 324 insertions, 0 deletions
diff --git a/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/core.py b/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/core.py new file mode 100644 index 0000000..4daba25 --- /dev/null +++ b/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/core.py @@ -0,0 +1,324 @@ +""" +Find the k-cores of a graph. + +The k-core is found by recursively pruning nodes with degrees less than k. + +See the following reference for details: + +An O(m) Algorithm for Cores Decomposition of Networks +Vladimir Batagelj and Matjaz Zaversnik, 2003. +http://arxiv.org/abs/cs.DS/0310049 + +""" +__author__ = "\n".join(['Dan Schult (dschult@colgate.edu)', + 'Jason Grout (jason-sage@creativetrax.com)', + 'Aric Hagberg (hagberg@lanl.gov)']) + +# Copyright (C) 2004-2010 by +# Aric Hagberg <hagberg@lanl.gov> +# Dan Schult <dschult@colgate.edu> +# Pieter Swart <swart@lanl.gov> +# All rights reserved. +# BSD license. +__all__ = ['core_number','k_core','k_shell','k_crust','k_corona','find_cores'] + +import networkx as nx + +def core_number(G): + """Return the core number for each vertex. + + A k-core is a maximal subgraph that contains nodes of degree k or more. + + The core number of a node is the largest value k of a k-core containing + that node. + + Parameters + ---------- + G : NetworkX graph + A graph or directed graph + + Returns + ------- + core_number : dictionary + A dictionary keyed by node to the core number. + + Raises + ------ + NetworkXError + The k-core is not defined for graphs with self loops or parallel edges. + + Notes + ----- + Not implemented for graphs with parallel edges or self loops. + + For directed graphs the node degree is defined to be the + in-degree + out-degree. + + References + ---------- + .. [1] An O(m) Algorithm for Cores Decomposition of Networks + Vladimir Batagelj and Matjaz Zaversnik, 2003. + http://arxiv.org/abs/cs.DS/0310049 + """ + if G.is_multigraph(): + raise nx.NetworkXError( + 'MultiGraph and MultiDiGraph types not supported.') + + if G.number_of_selfloops()>0: + raise nx.NetworkXError( + 'Input graph has self loops; the core number is not defined.', + 'Consider using G.remove_edges_from(G.selfloop_edges()).') + + if G.is_directed(): + import itertools + def neighbors(v): + return itertools.chain.from_iterable([G.predecessors_iter(v), + G.successors_iter(v)]) + else: + neighbors=G.neighbors_iter + degrees=G.degree() + # sort nodes by degree + nodes=sorted(degrees,key=degrees.get) + bin_boundaries=[0] + curr_degree=0 + for i,v in enumerate(nodes): + if degrees[v]>curr_degree: + bin_boundaries.extend([i]*(degrees[v]-curr_degree)) + curr_degree=degrees[v] + node_pos = dict((v,pos) for pos,v in enumerate(nodes)) + # initial guesses for core is degree + core=degrees + nbrs=dict((v,set(neighbors(v))) for v in G) + for v in nodes: + for u in nbrs[v]: + if core[u] > core[v]: + nbrs[u].remove(v) + pos=node_pos[u] + bin_start=bin_boundaries[core[u]] + node_pos[u]=bin_start + node_pos[nodes[bin_start]]=pos + nodes[bin_start],nodes[pos]=nodes[pos],nodes[bin_start] + bin_boundaries[core[u]]+=1 + core[u]-=1 + return core + +find_cores=core_number + +def k_core(G,k=None,core_number=None): + """Return the k-core of G. + + A k-core is a maximal subgraph that contains nodes of degree k or more. + + Parameters + ---------- + G : NetworkX graph + A graph or directed graph + k : int, optional + The order of the core. If not specified return the main core. + core_number : dictionary, optional + Precomputed core numbers for the graph G. + + Returns + ------- + G : NetworkX graph + The k-core subgraph + + Raises + ------ + NetworkXError + The k-core is not defined for graphs with self loops or parallel edges. + + Notes + ----- + The main core is the core with the largest degree. + + Not implemented for graphs with parallel edges or self loops. + + For directed graphs the node degree is defined to be the + in-degree + out-degree. + + Graph, node, and edge attributes are copied to the subgraph. + + See Also + -------- + core_number + + References + ---------- + .. [1] An O(m) Algorithm for Cores Decomposition of Networks + Vladimir Batagelj and Matjaz Zaversnik, 2003. + http://arxiv.org/abs/cs.DS/0310049 + """ + if core_number is None: + core_number=nx.core_number(G) + if k is None: + k=max(core_number.values()) # max core + nodes=(n for n in core_number if core_number[n]>=k) + return G.subgraph(nodes).copy() + +def k_shell(G,k=None,core_number=None): + """Return the k-shell of G. + + The k-shell is the subgraph of nodes in the k-core containing + nodes of exactly degree k. + + Parameters + ---------- + G : NetworkX graph + A graph or directed graph. + k : int, optional + The order of the shell. If not specified return the main shell. + core_number : dictionary, optional + Precomputed core numbers for the graph G. + + + Returns + ------- + G : NetworkX graph + The k-shell subgraph + + Raises + ------ + NetworkXError + The k-shell is not defined for graphs with self loops or parallel edges. + + Notes + ----- + This is similar to k_corona but in that case only neighbors in the + k-core are considered. + + Not implemented for graphs with parallel edges or self loops. + + For directed graphs the node degree is defined to be the + in-degree + out-degree. + + Graph, node, and edge attributes are copied to the subgraph. + + See Also + -------- + core_number + k_corona + + + ---------- + .. [1] A model of Internet topology using k-shell decomposition + Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, + and Eran Shir, PNAS July 3, 2007 vol. 104 no. 27 11150-11154 + http://www.pnas.org/content/104/27/11150.full + """ + if core_number is None: + core_number=nx.core_number(G) + if k is None: + k=max(core_number.values()) # max core + nodes=(n for n in core_number if core_number[n]==k) + return G.subgraph(nodes).copy() + +def k_crust(G,k=None,core_number=None): + """Return the k-crust of G. + + The k-crust is the graph G with the k-core removed. + + Parameters + ---------- + G : NetworkX graph + A graph or directed graph. + k : int, optional + The order of the shell. If not specified return the main crust. + core_number : dictionary, optional + Precomputed core numbers for the graph G. + + Returns + ------- + G : NetworkX graph + The k-crust subgraph + + Raises + ------ + NetworkXError + The k-crust is not defined for graphs with self loops or parallel edges. + + Notes + ----- + This definition of k-crust is different than the definition in [1]_. + The k-crust in [1]_ is equivalent to the k+1 crust of this algorithm. + + Not implemented for graphs with parallel edges or self loops. + + For directed graphs the node degree is defined to be the + in-degree + out-degree. + + Graph, node, and edge attributes are copied to the subgraph. + + See Also + -------- + core_number + + References + ---------- + .. [1] A model of Internet topology using k-shell decomposition + Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, + and Eran Shir, PNAS July 3, 2007 vol. 104 no. 27 11150-11154 + http://www.pnas.org/content/104/27/11150.full + """ + if core_number is None: + core_number=nx.core_number(G) + if k is None: + k=max(core_number.values())-1 + nodes=(n for n in core_number if core_number[n]<=k) + return G.subgraph(nodes).copy() + + +def k_corona(G, k, core_number=None): + """Return the k-crust of G. + + The k-corona is the subset of vertices in the k-core which have + exactly k neighbours in the k-core. + + Parameters + ---------- + G : NetworkX graph + A graph or directed graph + k : int + The order of the corona. + core_number : dictionary, optional + Precomputed core numbers for the graph G. + + Returns + ------- + G : NetworkX graph + The k-corona subgraph + + Raises + ------ + NetworkXError + The k-cornoa is not defined for graphs with self loops or + parallel edges. + + Notes + ----- + Not implemented for graphs with parallel edges or self loops. + + For directed graphs the node degree is defined to be the + in-degree + out-degree. + + Graph, node, and edge attributes are copied to the subgraph. + + See Also + -------- + core_number + + References + ---------- + .. [1] k -core (bootstrap) percolation on complex networks: + Critical phenomena and nonlocal effects, + A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes, + Phys. Rev. E 73, 056101 (2006) + http://link.aps.org/doi/10.1103/PhysRevE.73.056101 + """ + + if core_number is None: + core_number = nx.core_number(G) + nodes = (n for n in core_number + if core_number[n] >= k + and len([v for v in G[n] if core_number[v] >= k]) == k) + return G.subgraph(nodes).copy() |