Paper Info
Title
Sampling directed graphs with random walks.
Abstract
Despite recent efforts to characterize complex networks such as citation graphs or online social networks (OSNs), little attention has been given to developing tools that can be used to characterize directed graphs in the wild, where no pre-processed data is available. The presence of hidden incoming edges but observable outgoing edges poses a challenge to characterize large directed graphs through crawling, as existing sampling methods cannot cope with hidden incoming links. The driving principle behind our random walk (RW) sampling method is to construct, in real-time, an undirected graph from the directed graph such that the random walk on the directed graph is consistent with one on the undirected graph. We then use the RW on the undirected graph to estimate the outdegree distribution. Our algorithm accurately estimates outdegree distributions of a variety of real world graphs. We also study the hardness of indegree distribution estimation when indegrees are latent (i.e., incoming links are only observed as outgoing edges). We observe that, in the same scenarios, indegree distribution estimates are highly innacurate unless the directed graph is highly symmetrical. © 2012 IEEE.
Year
DOI
Venue
2012
10.1109/INFCOM.2012.6195540
Orlando, FL
Keywords
Field
DocType
random processes,sampling methods,directed graphs,complex networks,estimation theory,random walk,real time,world wide web,complex network,directed graph
Block graph,Discrete mathematics,Comparability graph,Combinatorics,Line graph,Path (graph theory),Computer science,Directed graph,Regular graph,Graph (abstract data type),Feedback arc set
Conference
Volume
Issue
ISSN
null
null
0743-166X
ISBN
Citations 
PageRank 
978-1-4673-0773-4
35
1.00
References 
Authors
7
4
Name
Order
Citations
PageRank
Bruno F. Ribeiro157241.35
Ping-Hui Wang223633.39
Fabricio Murai3718.15
Don Towsley4186931951.05