Clustering coefficients of large networks

Li, Yusheng, Shang, Yilun and Yang, Yiting (2017) Clustering coefficients of large networks. Information Sciences, 382. pp. 350-358. ISSN 0020-0255

[img]
Preview
Text (Full text)
Li et al - Clustering coefficients of large networks AAM.pdf - Accepted Version

Download (199kB) | Preview
Official URL: http://dx.doi.org/10.1016/j.ins.2016.12.027

Abstract

Let G be a network with n nodes and eigenvalues λ1 ≥ λ2 ≥ ⋅⋅⋅ ≥ λn. Then G is called an (n, d, λ)-network if it is d-regular and λ=max{|λ2|,|λ3|,⋯,|λn|}. It is shown that if G is an (n, d, λ)-network and λ=O(√d), the average clustering coefficient c¯(G) of G satisfies c¯(G)∼d/n for large d. We show that this description also holds for strongly regular graphs and Erdős–Rényi graphs. Although most real-world networks are not constructed theoretically, we find that many of them have c¯(G) close to d¯/n, and many close to 1−μ2¯(n−d¯−1)/d¯d¯−1), where d¯ is the average degree of G and μ2¯ is the average of the numbers of common neighbors over all non-adjacent pairs of nodes.

Item Type: Article
Uncontrolled Keywords: Clustering coefficient; theoretic graph; real-world network
Subjects: G400 Computer Science
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: Paul Burns
Date Deposited: 26 Oct 2018 16:56
Last Modified: 11 Oct 2019 18:02
URI: http://nrl.northumbria.ac.uk/id/eprint/36450

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics