1. bookVolume 12 (2020): Issue 1 (July 2020)
Journal Details
License
Format
Journal
eISSN
2066-7760
First Published
30 May 2014
Publication timeframe
2 times per year
Languages
English
access type Open Access

Efficiency centrality in time-varying graphs

Published Online: 16 Jul 2020
Volume & Issue: Volume 12 (2020) - Issue 1 (July 2020)
Page range: 5 - 21
Received: 19 Jan 2020
Accepted: 18 Feb 2020
Journal Details
License
Format
Journal
eISSN
2066-7760
First Published
30 May 2014
Publication timeframe
2 times per year
Languages
English
Abstract

One of the most studied aspect of complex graphs is identifying the most influential nodes. There are some local metrics like degree centrality, which is cost-effiective and easy to calculate, although using global metrics like betweenness centrality or closeness centrality can identify influential nodes more accurately, however calculating these values can be costly and each measure has it’s own limitations and disadvantages. There is an ever-growing interest in calculating such metrics in time-varying graphs (TVGs), since modern complex networks can be best modelled with such graphs. In this paper we are investigating the effectiveness of a new centrality measure called efficiency centrality in TVGs. To evaluate the performance of the algorithm Independent Cascade Model is used to simulate infection spreading in four real networks. To simulate the changes in the network we are deleting and adding nodes based on their degree centrality. We are investigating the Time-Constrained Coverage and the magnitude of propagation resulted by the use of the algorithm.

Keywords

MSC 2010

[1] A. Bavelas, Communication in task-oriented groups, The Journal of the Acoustical Society of America, 22, 6 (1950) 725–730. ⇒710.1121/1.1906679Search in Google Scholar

[2] P. Bonacich, Power and centrality: A family of measure, American journal of sociology, 92, 5 (1987) 1170–1182. ⇒610.1086/228631Search in Google Scholar

[3] S. P. Borgatti, Centrality and network flow, Social networks, 27, 1 (2005) 55–71. ⇒610.1016/j.socnet.2004.11.008Search in Google Scholar

[4] E. C. Costa, A. B. Vieira, K. Wehmuth, A.r Ziviani, A. P. Couto Da Silva, Time centrality in dynamic complex networks, Advances in Complex Systems, 18, 07n08 (2015), p. 1550023. ⇒6, 1110.1142/S021952591550023XSearch in Google Scholar

[5] L. C. Freeman, A set of measures of centrality based on betweenness, Sociometry, 40, 1 (1977) 35–41. ⇒610.2307/3033543Search in Google Scholar

[6] L. C. Freeman, Centrality in social networks conceptual clarification, Social networks, 1, 3 (1978) 215–239. ⇒610.1016/0378-8733(78)90021-7Search in Google Scholar

[7] N. E. Friedkin, Theoretical foundations for centrality measures, Americal journal of Sociology, 96, 6 (1991) 1478–1504. ⇒610.1086/229694Search in Google Scholar

[8] S. Gao, J. Ma, Z. Chen, G. Wang, C. Xing, Ranking the spreading ability of nodes in complex networks based on local structure, Physica A: Statistical Mechanics and its Applications, 403, (2014) 130–147. ⇒610.1016/j.physa.2014.02.032Search in Google Scholar

[9] D. Kempe, J. Kleinberg,É. Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, (2003) 137–146. ⇒1010.1145/956750.956769Search in Google Scholar

[10] B. Kósa, M. Balassi, P. Englert, G Rácz, Z Pusztai, A. Kiss, A basic network analytic package for rapidminer, Rapid Miner World, (2014) ⇒6Search in Google Scholar

[11] V. Latora, M. Marchiori, Efficent behavior of small-world networks, Physical review letters, 87, 19, (2001), p. 198701. ⇒8, 910.1103/PhysRevLett.87.19870111690461Search in Google Scholar

[12] J. Leskovec, A. Krevl, SNAP Datasets: Stanford large network dataset collection, (2014), http://snap.stanford.edu/data ⇒11Search in Google Scholar

[13] M. Nekovee, Y. Moreno, G. Bianconi, M. Marsili, Theory of rumour spreading in complex social networks, Physica A: Statistical Mechanics and its Applications, 374, 1 (2007) 457–470. ⇒610.1016/j.physa.2006.07.017Search in Google Scholar

[14] M. EJ. Newman, Mathematics of networks, The new Palgrave dictionary of economics, (2016) 1–8. ⇒710.1057/978-1-349-95121-5_2565-1Search in Google Scholar

[15] L. Page, S. Brin, R. Motwani, T. Winograd, The pagerank citation ranking: Bringing order to the web, Technical report, Standord InfoLab, (1999) ⇒6Search in Google Scholar

[16] R. A. Rossi, N- K. Ahmed, The network data repository with interactive graph analytics and visualization, (2015), http://networkrepository.com ⇒11Search in Google Scholar

[17] Ch. Song, S. Havlin, H. A. Makse, Self-similarity of complex networks, Nature, 443, 7024, (2005), p. 392. ⇒610.1038/nature0324815674285Search in Google Scholar

[18] S. Wang, Y. Du, Y. Deng, A new measure of identifying influential nodes: Efficiency centrality, Communications in Nonlinear Science and Numerical Simulation, 47, (2017) 151–163. ⇒6, 8, 11, 1210.1016/j.cnsns.2016.11.008Search in Google Scholar

[19] K. Wehmuth, A. Ziviani, E. Fleury, A unifying model for representing time-varying graphs, 2015 IEEE International Conference on Data Science and Advanced Analytics (DSAA), IEEE, (2015) 1–10. ⇒1010.1109/DSAA.2015.7344810Search in Google Scholar

[20] A. Zaki, M. Attia, D. Hegazy, S. Amin, Comprehensive survey on dynamic graph models, International Journal of Advanced Computer Science and Applications, 7, 2 (2016) 573–582. ⇒610.14569/IJACSA.2016.070273Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo