Fast discovery of connection subgraphs
Published 22 August 2004
Christos Faloutsos, Kevin S. McCurley, Andrew Tomkins
Citations360
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work defines a connection subgraph as a small subgraph of a large graph that best captures the relationship between two nodes, and presents a formal definition of this problem, and an ideal solution based on electricity analogues.
Abstract
We define a connection subgraph as a small subgraph of a large graph that best captures the relationship between two nodes. The primary motivation for this work is to provide a paradigm for exploration and knowledge discovery in large social networks graphs. We present a formal definition of this problem, and an ideal solution based on electricity analogues. We then show how to accelerate the computations, to produce approximate, but high-quality connection subgraphs in real time on very large (disk resident) graphs.We describe our operational prototype, and we demonstrate results on a social network graph derived from the World Wide Web. Our graph contains 15 million nodes and 96 million edges, and our system still produces quality responses within seconds.
Keywords
Computer SciencePhysics and Astronomy
SIAM ReviewThe Structure and Function of Complex Networks
18,742 Citations2003Michael Newman
Developments in this field are reviewed, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.
The PageRank Citation Ranking : Bringing Order to the Web
12,645 Citations1999Lawrence M. Page, Sergey Brin +2 more
This paper describes PageRank, a mathod for rating Web pages objectively and mechanically, effectively measuring the human interest and attention devoted to them, and shows how to efficiently compute PageRank for large numbers of pages.
Maximizing the spread of influence through a social network
7,314 Citations2003David Kempe, Jon Kleinberg +1 more
An analysis framework based on submodular functions shows that a natural greedy strategy obtains a solution that is provably within 63% of optimal for several classes of models, and suggests a general approach for reasoning about the performance guarantees of algorithms for these types of influence problems in social networks.
NatureDiameter of the World-Wide Web
4,285 Citations1999Réka Albert, Hawoong Jeong +1 more
The World-Wide Web becomes a large directed graph whose vertices are documents and whose edges are links that point from one document to another, which determines the web's connectivity and consequently how effectively the authors can locate information on it.
On power-law relationships of the Internet topology
4,222 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period, and can be used to generate and select realistic topologies for simulation purposes.
Advances In PhysicsEvolution of networks
3,140 Citations2002S. N. Dorogovt︠s︡ev, J. F. F. Mendes
The recent rapid progress in the statistical physics of evolving networks is reviewed, and how growing networks self-organize into scale-free structures is discussed, and the role of the mechanism of preferential linking is investigated.
Mining the network value of customers
2,868 Citations2001Pedro Domingos, Matt Richardson
It is proposed to model also the customer's network value: the expected profit from sales to other customers she may influence to buy, the customers those may influence, and so on recursively, taking advantage of the availability of large relevant databases.
ACM SIGCOMM Computer Communication ReviewOn power-law relationships of the Internet topology
2,599 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
The Carus mathematical monographsRandom Walks and Electric Networks
1,776 Citations1984Peter G. Doyle, J. Laurie Snell
Graph Clustering by Flow Simulation
1,608 Citations2000S.M. van Dongen
The link prediction problem for social networks
1,608 Citations2003David Liben‐Nowell, Jon Kleinberg
Experiments on large co-authorship networks suggest that information about future interactions can be extracted from network topology alone, and that fairly subtle measures for detecting node proximity can outperform more direct measures.
Topic-sensitive PageRank
1,524 Citations2002Taher H. Haveliwala
A set of PageRank vectors are proposed, biased using a set of representative topics, to capture more accurately the notion of importance with respect to a particular topic, and are shown to generate more accurate rankings than with a single, generic PageRank vector.
Scaling personalized web search
1,205 Citations2003Glen Jeh, Jennifer Widom
The approach enables incremental computation, so that the construction of personalized views from partial vectors is practical at query time, and experimental results demonstrate the effectiveness and scalability of the techniques.
Software Practice and ExperienceAn open graph visualization system and its applications to software engineering
1,103 Citations2000Emden R. Gansner, Stephen C. North
A package of practical tools and libraries for manipulating graphs and their drawings that includes stream and event interfaces for graph operations, high‐quality static and dynamic layout algorithms, and the ability to handle sizeable graphs is described.
ComputerSelf-organization and identification of Web communities
1,007 Citations2002Gary William Flake, Sandra Lawrence +2 more
This work shows that the Web self-organizes and its link structure allows efficient identification of communities and is significant because no central authority or process governs the formation and structure of hyperlinks.
Information-theoretic co-clustering
998 Citations2003Inderjit S. Dhillon, Subramanyam Mallela +1 more
This work presents an innovative co-clustering algorithm that monotonically increases the preserved mutual information by intertwining both the row and column clusterings at all stages and demonstrates that the algorithm works well in practice, especially in the presence of sparsity and high-dimensionality.
Inferring Web communities from link topology
772 Citations1998David Gibson, Jon Kleinberg +1 more
This investigation shows that although the process by which users of the Web create pages and links is very difficult to understand at a “local” level, it results in a much greater degree of orderly high-level structure than has typically been assumed.
Lecture notes in mathematicsDesign of Survivable Networks
378 Citations1992Mechthild Stoer
Network survivability models using node types under connectivity constraints - a survey and basic inequalities and implementation of the cutting plane algorithm are presented.
The electrical resistance of a graph captures its commute and cover times
357 Citations1989Ashok K. Chandra, Prabhakar Raghavan +2 more
SIAM ReviewParallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
351 Citations1999George Karypis, Vipin Kumar
A key feature of this parallel formulation is that it is able to achieve a high degree of concurrency while maintaining the high quality of the partitions produced by the serial multilevel k-way graph partitioning algorithm.
Lecture notes in computer scienceExperiments on Graph Clustering Algorithms
303 Citations2003Ulrik Brandes, Marco Gaertler +1 more
An experimental evaluation of graph clustering approaches is conducted and by combining proven techniques from graph partitioning and geometric clustering, a new approach is introduced that compares favorably.
IBM Systems JournalHow to build a WebFountain: An architecture for very large-scale text analytics
95 Citations2004Daniel Gruhl, L. Chavet +5 more
This paper surveys the high-level decisions made in creating a platform for very large-scale text analytics applications and creates an extensible set of hosted Web services containing information that drives end-user applications.
Clustering the Chilean Web
19 Citations2004Satu Elisa Virtanen
A clustering of the Chilean Web graph is performed using a local fitness measure, optimized by simulated annealing, and the obtained cluster distribution is compared to that of two models of the Web graph.