"""
Find the k-cores of a graph.
The k-core is found by recursively pruning nodes with degrees less than k.
"""
__author__ = "\n".join(['Dan Schult(dschult@colgate.edu)',
'Jason Grout(jason-sage@creativetrax.com)'])
# Copyright (C) 2004-2008 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__all__ = ['find_cores']
def find_cores(G):
"""Return the core number for each vertex.
Parameters
----------
G : NetworkX graph
A graph
Returns
-------
core_number : dictionary
A ditionary keyed by node to the 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
"""
# compute the degrees of each vertex
degrees=G.degree()
# sort verticies by degree
verts= sorted( degrees.keys(), key=lambda x: degrees[x])
bin_boundaries=[0]
curr_degree=0
for i,v in enumerate(verts):
if degrees[v]>curr_degree:
bin_boundaries.extend([i]*(degrees[v]-curr_degree))
curr_degree=degrees[v]
vert_pos = dict((v,pos) for pos,v in enumerate(verts))
# Set up initial guesses for core and lists of neighbors.
core= degrees
nbrs=dict((v,set(G.neighbors(v))) for v in G)
# form vertex core building up from smallest
for v in verts:
for u in nbrs[v]:
if core[u] > core[v]:
nbrs[u].remove(v)
pos=vert_pos[u]
bin_start=bin_boundaries[core[u]]
vert_pos[u]=bin_start
vert_pos[verts[bin_start]]=pos
verts[bin_start],verts[pos]=verts[pos],verts[bin_start]
bin_boundaries[core[u]]+=1
core[u] -= 1
return core
|