Generalized relationships between characteristic path length, efficiency, clustering coefficients, and density
Tóm tắt
Graph theoretic properties such as the clustering coefficient, characteristic (or average) path length, global and local efficiency provide valuable information regarding the structure of a graph. These four properties have applications to biological and social networks and have dominated much of the literature in these fields. While much work has done in applied settings, there has yet to be a mathematical comparison of these metrics from a theoretical standpoint. Motivated by both real-world data and computer simulations, we present asymptotic linear relationships between the characteristic path length, global efficiency, and graph density, and also between the clustering coefficient and local efficiency. In the current literature, these properties are often presented as independent metrics; however, we show in this paper that they are inextricably linked.
Tài liệu tham khảo
Bullmore E, Sporns O (2009) Complex brain networks: graph theoretical analysis of structural and functional systems. Nature 10:186–196
Ek B, VerSchneider C, Cahill N, Narayan DA (2015) A comprehensive comparison of graph theory metrics for social networks. Social Netw Anal Min 5(1):1-7
Bryan B Ek, VerSchneider C, Narayan DA (2015) Global efficiency of graphs. AKCE Int J Graphs Comb 12(1):1–13
Erdős P, Rényi A (1959) On random graphs. Publ Math 6:290–297
Fukami T, Takahashi N (2014) New classes of clustering coefficient locally maximizing graphs. Discrete Appl Math 162:202–213
Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78:046110
Latora V, Marchiori M (2001) Efficient behavior of small-world networks. Phys Rev Lett E 87(19):198701
Li Y, Shang Y, Yang Y (2017) Clustering coefficients of large networks. Inf Sci 382(383):350–358
McCarthy P (2014) Functional network analysis of aging and Alzeheimer’s disease. Ph.D. Thesis, University of Otago
McCarthy P, Benuskova L, Franz E (2014) The age-related posterior-anterior shift as revealed by voxelwise analysis of functional brain networks. Aging Neurosci. https://doi.org/10.3389/fnagi.2014.00301
Mariá Nascimento CV (2014) Community detection in networks via a spectral heuristic based on the clustering coefficient. Discrete Appl Math 176:89–99
Shang Y (2012) Distinct clustering and characteristic path lengths in dynamic small-world networks with identical limit degree distribution. J Stat Phys 149(3):505–518
Sporns O (2011) Networks of the brain. MIT Press, Cambridge
Vargas R, Garcea F, Mahon B, Narayan DA (2016) Refining the clustering coefficient for analysis of social and neural network data. Soc Netw Anal Min 6:49. https://doi.org/10.1007/s13278-016-0361-x
Watts D, Strogatz S (1998) Collective dynamics of ‘small world networks’. Nature 393:440–442
Zhang T, Fang B, Liang X (2015) A novel measure to identify influential nodes in complex networks based on network global efficiency. Modern Phys Lett B 29(28):1550168. https://doi.org/10.1142/S0217984915501687