Models of similarity in complex networks

被引:2
作者
Shvydun, Sergey [1 ,2 ]
机构
[1] HSE Univ, Moscow, Russia
[2] Delft Univ Technol, Delft, Netherlands
关键词
Network similarity; Complex networks; Graph distance; Structural network properties; Dynamics on and of complex networks; DISTANCE; GRAPHS;
D O I
10.7717/peerj-cs.1371
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The analysis of networks describing many social, economic, technological, biological and other systems has attracted a lot of attention last decades. Since most of these complex systems evolve over time, there is a need to investigate the changes, which appear in the system, in order to assess the sustainability of the network and to identify stable periods. In the literature, there have been developed a large number of models that measure the similarity among the networks. There also exist some surveys, which consider a limited number of similarity measures and then perform their correlation analysis, discuss their properties or assess their performances on synthetic benchmarks or real networks. The aim of the article is to extend these studies. The article considers 39 graph distance measures and compares them on simple graphs, random graph models and real networks. The author also evaluates the performance of the models in order to identify which of them can be applied to large networks. The results of the study reveal some important aspects of existing similarity models and provide a better understanding of their advantages and disadvantages. The major finding of the work is that many graph similarity measures of different nature are well correlated and that some comprehensive methods are well agreed with simple models. Such information can be used for the choice of appropriate similarity measure as well as for further development of new models for similarity assessment in network structures.
引用
收藏
页码:1 / 35
页数:35
相关论文
共 49 条
[11]   Assessing diversity in multiplex networks [J].
Carpi, Laura C. ;
Schieber, Tiago A. ;
Pardalos, Panos M. ;
Marfany, Gemma ;
Masoller, Cristina ;
Diaz-Guilera, Albert ;
Ravetti, Martin G. .
SCIENTIFIC REPORTS, 2019, 9 (1)
[12]   Analyzing complex networks evolution through Information Theory quantifiers [J].
Carpi, Laura C. ;
Rosso, Osvaldo A. ;
Saco, Patricia M. ;
Ravetti, Martin Gomez .
PHYSICS LETTERS A, 2011, 375 (04) :801-804
[13]  
Charikar M. S., 2002, Proceedings Of The Thiry-Fourth Annual ACM Symposium On Theory Of Computing, STOC '02, P380, DOI DOI 10.1145/509907.509965
[14]   Complex network comparison based on communicability sequence entropy [J].
Chen, Dan ;
Shi, Dan-Dan ;
Qin, Mi ;
Xu, Si-Meng ;
Pan, Gui-Jun .
PHYSICAL REVIEW E, 2018, 98 (01)
[15]   Families of Alpha- Beta- and Gamma- Divergences: Flexible and Robust Measures of Similarities [J].
Cichocki, Andrzej ;
Amari, Shun-ichi .
ENTROPY, 2010, 12 (06) :1532-1568
[16]   Metric axioms and distance [J].
Cullinane, Michael J. .
MATHEMATICAL GAZETTE, 2011, 95 (534) :414-419
[17]   Spectral Entropies as Information-Theoretic Tools for Complex Network Comparison [J].
De Domenico, Manlio ;
Biamonte, Jacob .
PHYSICAL REVIEW X, 2016, 6 (04)
[18]   Structural reducibility of multilayer networks [J].
De Domenico, Manlio ;
Nicosia, Vincenzo ;
Arenas, Alexandre ;
Latora, Vito .
NATURE COMMUNICATIONS, 2015, 6
[19]  
Deza M. M., 2009, ENCY DISTANCES, P1, DOI [DOI 10.1007/978-3-642-00234-2, 10.1007/978-3-662-44342-2]
[20]  
Donnat C, 2018, Arxiv, DOI arXiv:1801.07351