Preferential Attachment in Online Networks: Measurement and Explanations

J Kunegis, M Blattner, C. Moser

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

We perform an empirical study of the preferential attachment phenomenon in temporal networks and show that on the Web, networks follow a nonlinear preferential attachment model in which the exponent depends on the type of network considered. The classical preferential attachment model for networks by Barabási and Albert (1999) assumes a linear relationship between the number of neighbors of a node in a network and the probability of attachment. Although this assumption is widely made in Web Science and related fields, the underlying linearity is rarely measured. To fill this gap, this paper performs an empirical longitudinal (time-based) study on forty-seven diverse Web network datasets from seven network categories and including directed, undirected and bipartite networks. We show that contrary to the usual assumption, preferential attachment is nonlinear in the networks under consideration. Furthermore, we observe that the deviation from linearity is dependent on the type of network, giving sublinear attachment in certain types of networks, and superlinear attachment in others. Thus, we introduce the preferential attachment exponent β as a novel numerical network measure that can be used to discriminate different types of networks. We propose explanations for the behavior of that network measure, based on the mechanisms that underly the growth of the network in question. Copyright 2013 ACM.
Original languageEnglish
Title of host publicationProceedings of ACM WebSci'13
PublisherACM WebSci
Pages205-214
ISBN (Print)9781450318891
DOIs
Publication statusPublished - 2013
EventACM WebSci13 -
Duration: 1 Jan 20131 Jan 2013

Conference

ConferenceACM WebSci13
Period1/01/131/01/13

Cite this

Kunegis, J., Blattner, M., & Moser, C. (2013). Preferential Attachment in Online Networks: Measurement and Explanations. In Proceedings of ACM WebSci'13 (pp. 205-214). ACM WebSci. https://doi.org/10.1145/2464464.2464514
Kunegis, J ; Blattner, M ; Moser, C. / Preferential Attachment in Online Networks: Measurement and Explanations. Proceedings of ACM WebSci'13. ACM WebSci, 2013. pp. 205-214
@inproceedings{e967deb0f47943aeb10571debee01406,
title = "Preferential Attachment in Online Networks: Measurement and Explanations",
abstract = "We perform an empirical study of the preferential attachment phenomenon in temporal networks and show that on the Web, networks follow a nonlinear preferential attachment model in which the exponent depends on the type of network considered. The classical preferential attachment model for networks by Barab{\'a}si and Albert (1999) assumes a linear relationship between the number of neighbors of a node in a network and the probability of attachment. Although this assumption is widely made in Web Science and related fields, the underlying linearity is rarely measured. To fill this gap, this paper performs an empirical longitudinal (time-based) study on forty-seven diverse Web network datasets from seven network categories and including directed, undirected and bipartite networks. We show that contrary to the usual assumption, preferential attachment is nonlinear in the networks under consideration. Furthermore, we observe that the deviation from linearity is dependent on the type of network, giving sublinear attachment in certain types of networks, and superlinear attachment in others. Thus, we introduce the preferential attachment exponent β as a novel numerical network measure that can be used to discriminate different types of networks. We propose explanations for the behavior of that network measure, based on the mechanisms that underly the growth of the network in question. Copyright 2013 ACM.",
author = "J Kunegis and M Blattner and C. Moser",
year = "2013",
doi = "10.1145/2464464.2464514",
language = "English",
isbn = "9781450318891",
pages = "205--214",
booktitle = "Proceedings of ACM WebSci'13",
publisher = "ACM WebSci",

}

Kunegis, J, Blattner, M & Moser, C 2013, Preferential Attachment in Online Networks: Measurement and Explanations. in Proceedings of ACM WebSci'13. ACM WebSci, pp. 205-214, ACM WebSci13, 1/01/13. https://doi.org/10.1145/2464464.2464514

Preferential Attachment in Online Networks: Measurement and Explanations. / Kunegis, J; Blattner, M; Moser, C.

Proceedings of ACM WebSci'13. ACM WebSci, 2013. p. 205-214.

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Preferential Attachment in Online Networks: Measurement and Explanations

AU - Kunegis, J

AU - Blattner, M

AU - Moser, C.

PY - 2013

Y1 - 2013

N2 - We perform an empirical study of the preferential attachment phenomenon in temporal networks and show that on the Web, networks follow a nonlinear preferential attachment model in which the exponent depends on the type of network considered. The classical preferential attachment model for networks by Barabási and Albert (1999) assumes a linear relationship between the number of neighbors of a node in a network and the probability of attachment. Although this assumption is widely made in Web Science and related fields, the underlying linearity is rarely measured. To fill this gap, this paper performs an empirical longitudinal (time-based) study on forty-seven diverse Web network datasets from seven network categories and including directed, undirected and bipartite networks. We show that contrary to the usual assumption, preferential attachment is nonlinear in the networks under consideration. Furthermore, we observe that the deviation from linearity is dependent on the type of network, giving sublinear attachment in certain types of networks, and superlinear attachment in others. Thus, we introduce the preferential attachment exponent β as a novel numerical network measure that can be used to discriminate different types of networks. We propose explanations for the behavior of that network measure, based on the mechanisms that underly the growth of the network in question. Copyright 2013 ACM.

AB - We perform an empirical study of the preferential attachment phenomenon in temporal networks and show that on the Web, networks follow a nonlinear preferential attachment model in which the exponent depends on the type of network considered. The classical preferential attachment model for networks by Barabási and Albert (1999) assumes a linear relationship between the number of neighbors of a node in a network and the probability of attachment. Although this assumption is widely made in Web Science and related fields, the underlying linearity is rarely measured. To fill this gap, this paper performs an empirical longitudinal (time-based) study on forty-seven diverse Web network datasets from seven network categories and including directed, undirected and bipartite networks. We show that contrary to the usual assumption, preferential attachment is nonlinear in the networks under consideration. Furthermore, we observe that the deviation from linearity is dependent on the type of network, giving sublinear attachment in certain types of networks, and superlinear attachment in others. Thus, we introduce the preferential attachment exponent β as a novel numerical network measure that can be used to discriminate different types of networks. We propose explanations for the behavior of that network measure, based on the mechanisms that underly the growth of the network in question. Copyright 2013 ACM.

U2 - 10.1145/2464464.2464514

DO - 10.1145/2464464.2464514

M3 - Conference contribution

SN - 9781450318891

SP - 205

EP - 214

BT - Proceedings of ACM WebSci'13

PB - ACM WebSci

ER -

Kunegis J, Blattner M, Moser C. Preferential Attachment in Online Networks: Measurement and Explanations. In Proceedings of ACM WebSci'13. ACM WebSci. 2013. p. 205-214 https://doi.org/10.1145/2464464.2464514