Sampling from large graphs

By Jure Leskovec, Christos Faloutsos. 2006

1,368 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Is the Sample Good Enough? Comparing Data from Twitter's Streaming API with Twitter's Firehose (2013, background): “(Leskovec and Faloutsos 2006) proposes a strategy for sampling large graphs to preserve network measures.”
Truthy: mapping the spread of astroturf in microblog streams (2010, background): “While the process of sampling edges (tweets between users) from a network to investigate structural properties has been shown to produce suboptimal approximations of true network characteristics [33], we find that the analyses described below are able to produce accurate classifications of truthy me”
Spectral Embedding of Signed Networks (2015, methodology): “We sample subgraphs of these two real-world datasets using forest-fire sampling [10], which can be understood as creating a version of the graph as it would have been at some previous time in its growth.”
Graph Learning: A Survey (2021, methodology): “For GSP, it is significant to design suitable graph sampling methods to preserve the features of the original graph, which aims at recovering the original graph efficiently [16].”
Network resilience (2020, methodology): “Serval sampling methods, such as random walk [853], breadth-first sampling [854], and scaling-down sampling [851], has been pro-”
PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text (2019, neutral): “(Leskovec and Faloutsos, 2006) and local partitioning (Andersen et al.”
GraphSAINT: Graph Sampling Based Inductive Learning Method (2019, background): “There are numerous random walk based samplers proposed in the literature (Ribeiro & Towsley, 2010; Leskovec & Faloutsos, 2006; Hu & Lau, 2013; Li et al., 2015).”
Advances in Social Networks Analysis and Mining ( ASONAM ) DE-Crawler : A Densification-Expansion Algorithm for Online Data Collection (2018, background): “Leskovec and Faloutsos study the characteristics of different algorithms under the down-sampling scenario [6].”
Generalized Louvain method for community detection in large networks (2011, background): “Results obtained by analyzing several real-world networks [20], [21] are summarized in Table I.”
Learning to Exploit Long-term Relational Dependencies in Knowledge Graphs (2019, methodology): “Random PageRank sampling is an efﬁcient algorithm for large graph sampling (Leskovec & Faloutsos, 2006 ples entities according to the PageRank weights and assigns higher biases to more valuable entities.”
Sampling Content from Online Social Networks (2015, background): “With the advent of large networked systems, there have been several studies on sampling large networks such as the Web-graph [Rusmevichientong et al. 2001] and social networks [Frank 1978; Gjoka et al. 2010; Granovetter 1976; Leskovec and Faloutsos 2006].”
A benchmarking study of embedding-based entity alignment for knowledge graphs (2020, positive): “For evaluation, we design two baseline methods on the basis of existing graph sampling algorithms [41]: • Random alignment sampling (RAS) (cid:12)rst randomly selects a (cid:12)xed size (e.g., 15K) of entity alignment between two KGs, and then extracts the relation triples whose head and tail…”
When Social Influence Meets Item Inference (2015, background): “readthFirst-Search(BFS)and Random Walk(RW)(and itsvariations) have been adopted by many crawlers to generate released datasets for OSNs [8, 25], Web [16], P2P networks [28], and other types of graphs [20]. However, BFS and RW tend to introduce a bias toward high-degree nodes [7, 19] with a higher pr”
Empirical Evaluation and New Design for Fighting Evolving Twitter Spammers (2011, methodology): “In order to decrease the effect of possible sampling bias [30], our crawler recursively collects Twitter accounts in multiple rounds, with the consideration of guaranteeing sampling randomness and maintaining social relationships, rather than simply using the Breath First Search (BFS) sampling techn”
Walking in Facebook: A Case Study of Unbiased Sampling of OSNs (2010, methodology): “They have been used for sampling the Web [15], P2P networks [8], [16], [17], and other large graphs [18].”
GroupINN: Grouping-based Interpretable Neural Network for Classification of Limited, Noisy Brain Data (2019, positive): “As it is presented in the literature [20], random walk is a useful tool to sample graph structures.”
Attention Models in Graphs (2018, background): “Inthereal-world, however, graphs can be both structurally large and complex [Ahmed et al. 2014; Leskovec and Faloutsos 2006] as well as noisy [He and Kempe 2014].”