|
|
|
| Vital Node Detection and Evolution Analysis in Dynamic Networks Based on PageRank |
| Wang Yu, Liu Dongsu |
| School of Economics and Management, Xidian University, Xi’an 710071 |
|
|
|
|
Abstract The PageRank algorithm is widely used to detect vital nodes in static networks. Finding out a manner in which this algorithm can be extended to detect vital nodes in dynamic networks is a significant task. Two dynamic PageRank centrality definitions are separately proposed based on network reconstruction and random walk policy reconstruction. Then, a segmented least squares algorithm is presented to characterize the evolution process and predict the trends of nodes’ centrality. Dynamic co-author networks are constructed in the Library and Information fields to verify the effectiveness of our two dynamic centrality definitions. We compare the trends of author influence obtained by our methods with real-world trends. Our experiments demonstrate that using our definitions, we could characterize the evolution process and more accurately predict the trends of nodes’ centrality.
|
|
Received: 22 December 2017
|
|
|
|
[1] Bonacich P.Some unique properties of eigenvector centrality[J]. Social Networks, 2007, 29(4): 555-564.
[2] Katz L.A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39-43.
[3] Freeman L C.A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41.
[4] Dorogovtsev S N, Goltsev A V, Mendes J F F. K-core organization of complex networks[J]. Physical Review Letters, 2006, 96(4): 40601.
[5] Brin S, Page L.The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks and ISDN systems, 1998, 30(1-7): 107-117.
[6] Lü L Y, Zhang Y C, Yeung C H, et al.Leaders in social networks the delicious case[J]. PLoS ONE, 2011, 6(6): e21202.
[7] Kleinberg J M.Authoritative sources in a hyperlinked environment[J]. Journal of the ACM, 1999, 46(5): 604-632.
[8] Bian T, Hu J T, Deng Y.Identifying influential nodes in complex networks based on AHP[J]. Physica A: Statistical Mechanics and its Applications, 2017, 479: 422-436.
[9] Liu H L, Ma C, Xiang B B, et al.Identifying multiple influential spreaders based on generalized closeness centrality[J]. Physica A: Statistical Mechanics and its Applications, 2018, 492: 2237-2248.
[10] Wang Z X, Du C J, Fan J P, et al.Ranking influential nodes in social networks based on node position and neighborhood[J]. Neurocomputing, 2017, 260: 466-477.
[11] Lü L Y, Chen D B, Ren X L, et al.Vital nodes identification in complex networks[J]. Physics Reports, 2016, 650: 1-63.
[12] Mariani M S, Medo M, Zhang Y C.Ranking nodes in growing networks: When PageRank fails[J]. Scientific reports, 2015, 5: 16181.
[13] Holme P, Saramäki J.Temporal networks[J]. Physics Reports, 2012, 519(3): 97-125.
[14] Mariani M S, Medo M, Zhang Y C.Identification of milestone papers through time-balanced network centrality[J]. Journal of Informetrics, 2016, 10(4): 1207-1223.
[15] Taylor D, Myers S A, Clauset A, et al.Eigenvector-based centrality measures for temporal networks[J]. Multiscale Modeling & Simulation, 2017, 15(1): 537-574.
[16] Kim M S, Han J W.A particle-and-density based evolutionary clustering method for dynamic networks[C]// Proceedings of the VLDB Endowment, Lyon, 2009: 622-633.
[17] Ma N, Guan J C, Zhao Y.Bringing PageRank to the citation analysis[J]. Information Processing and Management, 2008, 44(2): 800-810.
[18] Meyer C D.Matrix analysis and applied linear algebra[M]. Philadelphia: The Society for Industrial and Applied Mathematics, 2000: 661-669.
[19] Kleinberg J, Tardos E.Algorithm Design[M]. Boston: Pearson Education, Inc., 2006: 261-266.
[20] Manning C D, Raghavan P, Schütze H.Introduction to Information Retrieval[M]. Cambridge: Cambridge University Press, 2009: 154-155. |
|
|
|
