research-article

Raising Graphs From Randomness to Reveal Information Networks

Authors:

Róbert Pálovics,

András A. BenczúrAuthors Info & Claims

WSDM '17: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining

Pages 23 - 32

https://doi.org/10.1145/3018661.3018664

Published: 02 February 2017 Publication History

Abstract

We analyze the fine-grained connections between the average degree and the power-law degree distribution exponent in growing information networks. Our starting observation is a power-law degree distribution with a decreasing exponent and increasing average degree as a function of the network size. Our experiments are based on three Twitter at-mention networks and three more from the Koblenz Network Collection. We observe that popular network models cannot explain decreasing power-law degree distribution exponent and increasing average degree at the same time.

We propose a model that is the combination of exponential growth, and a power-law developing network, in which new "homophily" edges are continuously added to nodes proportional to their current homophily degree. Parameters of the average degree growth and the power-law degree distribution exponent functions depend on the ratio of the network growth exponent parameters. Specifically, we connect the growth of the average degree to the decreasing exponent of the power-law degree distribution. Prior to our work, only one of the two cases were handled. Existing models and even their combinations can only reproduce some of our key new observations in growing information networks.

References

[1]

P. Aragón, K. E. Kappler, A. Kaltenbrunner, D. Laniado, and Y. Volkovich. Communication dynamics in twitter during political campaigns: The case of the 2011 Spanish national election. Policy & Internet, 5(2):183--206, 2013.

[2]

E. Bakshy, J. M. H., W. A. Mason, and D. J. Watts. Everyone's an influencer: quantifying influence on Twitter. In Proceedings of WSDM 2011, pages 65--74. ACM, 2011.

Digital Library

[3]

A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509--512, 1999.

[4]

A.-L. Barabâsi, H. Jeong, Z. Néda, E. Ravasz, A. Schubert, and T. Vicsek. Evolution of the social network of scientific collaborations. Physica A: Statistical mechanics and its applications, 311(3):590--614, 2002.

[5]

M. Cha, H. Haddadi, F. Benevenuto, and K. Gummadi. Measuring user influence in Twitter: The million follower fallacy. In ICWSM, 2010.

[6]

M. Cha, A. Mislove, B. Adams, and K. P. Gummadi. Characterizing social cascades in Flickr. In Proceedings of the first workshop on Online social networks, pages 13--18. ACM, 2008.

Digital Library

[7]

F. R. Chung and L. Lu. Complex graphs and networks, volume 107. American Mathematical Society, Providence, 2006.

[8]

A. Clauset, C. R. Shalizi, and M. E. Newman. Power-law distributions in empirical data. SIAM review, 51(4):661--703, 2009.

Digital Library

[9]

S. N. Dorogovtsev and J. Mendes. Accelerated growth of networks. arXiv preprint cond-mat/0204102, 2002.

[10]

S. N. Dorogovtsev and J. F. F. Mendes. Scaling behaviour of developing and decaying networks. EPL, 52(1):33, 2000.

[11]

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

[12]

R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the web graph. In Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, pages 57--65. IEEE, 2000.

[13]

J. Kunegis. Konect: the koblenz network collection. In Proceedings of WWW 2013, pages 1343--1350. International World Wide Web Conferences Steering Committee, 2013.

Digital Library

[14]

H. Kwak, C. Lee, H. Park, and S. Moon. What is twitter, a social network or a news media? In Proceedings of WWW 2010, pages 591--600. ACM, 2010.

Digital Library

[15]

J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM TKDD, 1(1):2, 2007.

Digital Library

[16]

D. Liben-Nowell and J. Kleinberg. Tracing information flow on a global scale using internet chain-letter data. PNAS, 105(12):4633--4638, 2008.

[17]

M. E. Newman. Power laws, pareto distributions and Zipf's law. Contemporary physics, 46(5):323--351, 2005.

[18]

P. Pedarsani, D. R. Figueiredo, and M. Grossglauser. Densification arising from sampling fixed graphs. In ACM SIGMETRICS Performance Evaluation Review, volume 36, pages 205--216. ACM, 2008.

Digital Library

[19]

C. Petersen, J. G. Simonsen, and C. Lioma. Power law distributions in information retrieval. ACM TOIS, 34(2):8, 2016.

Digital Library

[20]

É. Rácz, J. Kertész, and Z. Eisler. A shift-optimized Hill-type estimator. arXiv preprint arXiv:0905.3096, 2009.

[21]

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

[22]

A. Vazquez. Statistics of citation networks. arXiv preprint cond-mat/0105031, 2001.

[23]

A. Vázquez. Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations. Physical Review E, 67(5):056104, 2003.

[24]

A. Vázquez, R. Pastor-Satorras, and A. Vespignani. Large-scale topological and dynamical properties of the Internet. Physical Review E, 65(6):066130, 2002.

Cited By

Huang XWang CSun QLi YLi W(2021)Temporal Analysis of Knowledge Networks2021 IEEE International Conference on Big Knowledge (ICBK)10.1109/ICKG52313.2021.00034(190-197)Online publication date: Dec-2021
https://doi.org/10.1109/ICKG52313.2021.00034
Haruna TGunji Y(2019)Ordinal Preferential Attachment: A Self-Organizing Principle Generating Dense Scale-Free NetworksScientific Reports10.1038/s41598-019-40716-19:1Online publication date: 11-Mar-2019
https://doi.org/10.1038/s41598-019-40716-1

Index Terms

Raising Graphs From Randomness to Reveal Information Networks

Recommendations

X-distribution: Retraceable Power-law Exponent of Complex Networks
Network modeling has been explored extensively by means of theoretical analysis as well as numerical simulations for Network Reconstruction (NR). The network reconstruction problem requires the estimation of the power-law exponent (γ) of a given input ...
Genetic algorithm for sampling from scale-free data and networks
GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

A variety of real-world data and networks can be described by a heavy-tailed probability distribution of its values, vertex degrees, or other significant properties, that follows the power law. Such a scale-free data and networks can be found in both ...
Degree distribution of large networks generated by the partial duplication model

In this paper, we present a rigorous analysis on the limiting behavior of the degree distribution of the partial duplication model, a random network growth model in the duplication and divergence family that is popular in the study of biological ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WSDM '17: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining

February 2017

868 pages

ISBN:9781450346757

DOI:10.1145/3018661

General Chairs:
Maarten de Rijke
University of Amsterdam
,
Milad Shokouhi
Microsoft
,
Program Chairs:
Andrew Tomkins
Google
,
Min Zhang
Tsinghua University

Copyright © 2017 ACM.

© 2017 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 February 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

``Big Data---Momentum' grant of the Hungarian Academy of Sciences
Trends in Social Media

Conference

WSDM 2017

Sponsor:

WSDM 2017: Tenth ACM International Conference on Web Search and Data Mining

February 6 - 10, 2017

Cambridge, United Kingdom

Acceptance Rates

WSDM '17 Paper Acceptance Rate 80 of 505 submissions, 16%;

Overall Acceptance Rate 498 of 2,863 submissions, 17%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
248
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang XWang CSun QLi YLi W(2021)Temporal Analysis of Knowledge Networks2021 IEEE International Conference on Big Knowledge (ICBK)10.1109/ICKG52313.2021.00034(190-197)Online publication date: Dec-2021
https://doi.org/10.1109/ICKG52313.2021.00034
Haruna TGunji Y(2019)Ordinal Preferential Attachment: A Self-Organizing Principle Generating Dense Scale-Free NetworksScientific Reports10.1038/s41598-019-40716-19:1Online publication date: 11-Mar-2019
https://doi.org/10.1038/s41598-019-40716-1

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