Paper Info
Title
Connectivity structure of bipartite graphs via the KNC-plot
Abstract
In this paper we introduce the k-neighbor connectivity plot, or KNC-plot, as a tool to study the macroscopic connectiv-ity structure of sparse bipartite graphs. Given a bipartite graph G = (U, V, E), we say that two nodes in U are k-neighbors if there exist at least k distinct length-two paths between them; this defines a k-neighborhood graph on U where the edges are given by the k-neighbor relation. For example, in a bipartite graph of users and interests, two users are k-neighbors if they have at least k common interests. The KNC-plot shows the degradation of connectivity of the graph as a function of k. We show that this tool provides an effective and interpretable high-level characterization of the connectivity of a bipartite graph However, naive algorithms to compute the KNC-plot are inefficient for k 1. We give an efficient and practical algorithm that runs in sub-quadratic time O(|E|2-1/k) and is a non-trivial improvement over the obvious quadratic-time algorithms for this problem. We prove significant improvements in this runtime for graphs with power-law degree distributions, and give a different algorithm with near-linear runtime when V grows slowly as a function of the size of the graph We compute the KNC-plot of four large real-world bipartite graphs, and discuss the structural properties of these graphs that emerge. We conclude that the KNC-plot represents a useful and practical tool for macroscopic analysis of large bipartite graphs.
Year
DOI
Venue
2008
10.1145/1341531.1341550
WSDM
Keywords
Field
DocType
different algorithm,connectivity structure,k common interest,k-neighbor connectivity plot,bipartite graph,k distinct length-two path,large bipartite graph,practical tool,k-neighborhood graph,sparse bipartite graph,large real-world bipartite graph,connectivity,connected components,bipartite graphs,power law,connected component
Data mining,Complete bipartite graph,Combinatorics,Line graph,Edge-transitive graph,Forbidden graph characterization,Computer science,Bipartite graph,Matching (graph theory),Theoretical computer science,Cograph,Dense graph
Conference
Citations 
PageRank 
References 
11
1.12
14
Authors
3
Name
Order
Citations
PageRank
Ravi Kumar1139321642.48
Andrew Tomkins293881401.23
Erik Vee374743.61