More Web Proxy on the site http://driver.im/

Article

Graphs over time: densification laws, shrinking diameters and possible explanations

Authors:

Christos FaloutsosAuthors Info & Claims

KDD '05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining

Pages 177 - 187

https://doi.org/10.1145/1081870.1081893

Published: 21 August 2005 Publication History

Abstract

How do real graphs evolve over time? What are "normal" growth patterns in social, technological, and information networks? Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network, or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time.Here we study a wide range of real graphs, and we observe some surprising phenomena. First, most of these graphs densify over time, with the number of edges growing super-linearly in the number of nodes. Second, the average distance between nodes often shrinks over time, in contrast to the conventional wisdom that such distance parameters should increase slowly as a function of the number of nodes (like O(log n) or O(log(log n)).Existing graph generation models do not exhibit these types of behavior, even at a qualitative level. We provide a new graph generator, based on a "forest fire" spreading process, that has a simple, intuitive justification, requires very few parameters (like the "flammability" of nodes), and produces graphs exhibiting the full range of properties observed both in prior work and in the present study.

References

[1]

J. Abello, A. L. Buchsbaum, and J. Westbrook. A functional approach to external graph algorithms. In Proceedings of the 6th Annual European Symposium on Algorithms, pages 332--343. Springer-Verlag, 1998.]]

Digital Library

[2]

J. Abello, P. M. Pardalos, and M. G. C. Resende. Handbook of massive data sets. Kluwer, 2002.]]

Digital Library

[3]

R. Albert and A.-L. Barabasi. Emergence of scaling in random networks. Science, pages 509--512, 1999.]]

[4]

R. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the world-wide web. Nature, 401:130--131, September 1999.]]

[5]

Z. Bi, C. Faloutsos, and F. Korn. The dgx distribution for mining massive, skewed data. In KDD, pages 17--26, 2001.]]

Digital Library

[6]

B. Bollobas and O. Riordan. The diameter of a scale-free random graph. Combinatorica, 24(1):5--34, 2004.]]

Digital Library

[7]

A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web: experiments and models. In Proceedings of World Wide Web Conference, 2000.]]

Digital Library

[8]

D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-mat: A recursive model for graph mining. In SDM, 2004.]]

[9]

F. Chung and L. Lu. The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences, 99(25):15879--15882, 2002.]]

[10]

C. Cooper and A. Frieze. A general model of web graphs. Random Struct. Algorithms, 22(3):311--335, 2003.]]

Digital Library

[11]

M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. In SIGCOMM, pages 251--262, 1999.]]

Digital Library

[12]

J. Gehrke, P. Ginsparg, and J. M. Kleinberg. Overview of the 2003 kdd cup. SIGKDD Explorations, 5(2):149--151, 2003.]]

Digital Library

[13]

B. H. Hall, A. B. Jaffe, and M. Trajtenberg. The nber patent citation data file: Lessons, insights and methodological tools. NBER Working Papers 8498, National Bureau of Economic Research, Inc, Oct. 2001.]]

[14]

B. A. Huberman and L. A. Adamic. Growth dynamics of the world-wide web. Nature, 399:131, 1999.]]

[15]

J. S. Katz. The self-similar science system. Research Policy, 28:501--517, 1999.]]

[16]

J. S. Katz. Scale independent bibliometric indicators. Measurement: Interdisciplinary Research and Perspectives, 3:24--28, 2005.]]

[17]

J. M. Kleinberg. Small-world phenomena and the dynamics of information. In Advances in Neural Information Processing Systems 14, 2002.]]

[18]

J. M. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. The web as a graph: Measurements, models, and methods. In Proc. International Conference on Combinatorics and Computing, pages 1--17, 1999.]]

[19]

R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the web graph. In Proc. 41st IEEE Symp. on Foundations of Computer Science, 2000.]]

Digital Library

[20]

R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Trawling the web for emerging cyber-communities. In Proceedings of 8th International World Wide Web Conference, 1999.]]

Digital Library

[21]

F. Menczer. Growing and navigating the small world web by local content. Proceedings of the National Academy of Sciences, 99(22):14014--14019, 2002.]]

[22]

S. Milgram. The small-world problem. Psychology Today, 2:60--67, 1967.]]

[23]

M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions, 2004.]]

[24]

M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.]]

Digital Library

[25]

A. Ntoulas, J. Cho, and C. Olston. What's new on the web? the evolution of the web from a search engine perspective. In WWW Conference, pages 1--12, New York, New York, May 2004.]]

Digital Library

[26]

U. of Oregon Route Views Project. Online data and reports. http://www.routeviews.org.]]

[27]

C. R. Palmer, P. B. Gibbons, and C. Faloutsos. Anf: A fast and scalable tool for data mining in massive graphs. In SIGKDD, Edmonton, AB, Canada, 2002.]]

Digital Library

[28]

S. Redner. Citation statistics from more than a century of physical review. Technical Report physics/0407137, arXiv, 2004.]]

[29]

M. Schroeder. Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise. W.H. Freeman and Company, New York, 1991.]]

[30]

D. J. Watts, P. S. Dodds, and M. E. J. Newman. Collective dynamics of 'small-world' networks. Nature, 393:440--442, 1998.]]

[31]

D. J. Watts, P. S. Dodds, and M. E. J. Newman. Identity and search in social networks. Science, 296:1302--1305, 2002.]]

Cited By

Rodríguez ADiaconescu ARodríguez JGómez J(2025)Correlating node centrality metrics with node resilience in self-healing systems with limited neighbourhood informationFuture Generation Computer Systems10.1016/j.future.2024.107553163(107553)Online publication date: Feb-2025
https://doi.org/10.1016/j.future.2024.107553
Ding PZhang JZhang PLv YWang D(2025)A stacked graph neural network with self-exciting process for robotic cognitive strategy reasoning in proactive human-robot collaborative assemblyAdvanced Engineering Informatics10.1016/j.aei.2024.10295763(102957)Online publication date: Jan-2025
https://doi.org/10.1016/j.aei.2024.102957
Araya ETyagi H(2024)Graph Matching via convex relaxation to the simplexFoundations of Data Science10.3934/fods.2024034(0-0)Online publication date: 2024
https://doi.org/10.3934/fods.2024034
Show More Cited By

Index Terms

Graphs over time: densification laws, shrinking diameters and possible explanations
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Graph evolution: Densification and shrinking diameters

How do real graphs evolve over time? What are normal growth patterns in social, technological, and information networks? Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network or in a very ...
Agwan: a generative model for labelled, weighted graphs
NFMCP'13: Proceedings of the 2nd International Conference on New Frontiers in Mining Complex Patterns

Real-world graphs or networks tend to exhibit a well-known set of properties, such as heavy-tailed degree distributions, clustering and community formation. Much effort has been directed into creating realistic and tractable models for unlabelled graphs,...
Same Stats, Different Graphs: (Graph Statistics and Why We Need Graph Drawings)
Graph Drawing and Network Visualization
Abstract
Data analysts commonly utilize statistics to summarize large datasets. While it is often sufficient to explore only the summary statistics of a dataset (e.g., min/mean/max), Anscombe’s Quartet demonstrates how such statistics can be misleading. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining

August 2005

844 pages

ISBN:159593135X

DOI:10.1145/1081870

General Chair:
Robert Grossman
University of Illinois at Chicago & Open Data Partners, USA
,
Program Chairs:
Roberto Bayardo
IBM Almaden Research, USA
,
Kristin Bennett
RPI, USA

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 August 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

KDD05

Sponsor:

KDD05: The Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 21 - 24, 2005

Illinois, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1,529
Total Citations
View Citations
6,903
Total Downloads

Downloads (Last 12 months)366
Downloads (Last 6 weeks)44

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rodríguez ADiaconescu ARodríguez JGómez J(2025)Correlating node centrality metrics with node resilience in self-healing systems with limited neighbourhood informationFuture Generation Computer Systems10.1016/j.future.2024.107553163(107553)Online publication date: Feb-2025
https://doi.org/10.1016/j.future.2024.107553
Ding PZhang JZhang PLv YWang D(2025)A stacked graph neural network with self-exciting process for robotic cognitive strategy reasoning in proactive human-robot collaborative assemblyAdvanced Engineering Informatics10.1016/j.aei.2024.10295763(102957)Online publication date: Jan-2025
https://doi.org/10.1016/j.aei.2024.102957
Araya ETyagi H(2024)Graph Matching via convex relaxation to the simplexFoundations of Data Science10.3934/fods.2024034(0-0)Online publication date: 2024
https://doi.org/10.3934/fods.2024034
Gu YLao XZhuo LLi XDeng C(2024)Construction and Change Analysis of Water Ecosystem Service Flow Networks in the Xiangjiang River Basin (XRB)Sustainability10.3390/su1609381316:9(3813)Online publication date: 1-May-2024
https://doi.org/10.3390/su16093813
Zhao NLuo TWang HYang SXiong NJing MWang J(2024)Synergistic Integration of Local and Global Information for Critical Edge IdentificationEntropy10.3390/e2611093326:11(933)Online publication date: 31-Oct-2024
https://doi.org/10.3390/e26110933
Okumuş FKarcı Ş(2024)MDSA: A Dynamic and Greedy Approach to Solve the Minimum Dominating Set ProblemApplied Sciences10.3390/app1420925114:20(9251)Online publication date: 11-Oct-2024
https://doi.org/10.3390/app14209251
Raghebi ZBanaei-Kashani F(2024)ActiveReach: an active learning framework for approximate reachability query answering in large-scale graphsFrontiers in Big Data10.3389/fdata.2024.14271047Online publication date: 19-Nov-2024
https://doi.org/10.3389/fdata.2024.1427104
Wu XWu HWang RZhou XLu K(2024)Towards adaptive graph neural networks via solving prior-data conflicts通过解决先验数据冲突实现自适应图神经网络Frontiers of Information Technology & Electronic Engineering10.1631/FITEE.230019425:3(369-383)Online publication date: 23-Mar-2024
https://doi.org/10.1631/FITEE.2300194
Yang JZhong MZhu YQian TLiu MYu J(2024)Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic ComputationProceedings of the VLDB Endowment10.14778/3681954.368196717:11(2840-2853)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681967
He XGhasemian ALee ESchwarze AClauset AMucha P(2024)Link prediction accuracy on real-world networks under non-uniform missing-edge patternsPLOS ONE10.1371/journal.pone.030688319:7(e0306883)Online publication date: 18-Jul-2024
https://doi.org/10.1371/journal.pone.0306883
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents