Clustering coefficients of large networks

Yusheng Li, Yilun Shang, Yiting Yang

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)
35 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)350-358
Number of pages9
JournalInformation Sciences
Volume382-383
Early online date15 Dec 2016
DOIs
Publication statusPublished - Mar 2017

Fingerprint

Dive into the research topics of 'Clustering coefficients of large networks'. Together they form a unique fingerprint.

Cite this