Identifying Vital Nodes on Temporal Networks: An Edge-Based K-Shell Decomposition
详细信息 查看官网全文
- 英文论文题名：Identifying Vital Nodes on Temporal Networks: An Edge-Based K-Shell Decomposition
- 论文作者：Zhanghui Ye ; Xiuxiu Zhan ; Yinzuo Zhou ; Chuang Liu ; Zi-Ke Zhang
- 英文论文作者：Zhanghui Ye ; Xiuxiu Zhan ; Yinzuo Zhou ; Chuang Liu ; Zi-Ke Zhang ; Alibaba Research Center for Complexity Sciences ; Hangzhou Normal University ; Key Laboratory of Public Security Information Application Based on Big-data Architecture ; Ministry of Public Security
- 年：2017
- 作者机构：Alibaba Research Center for Complexity Sciences,Hangzhou Normal University;Key Laboratory of Public Security Information Application Based on Big-data Architecture,Ministry of Public Security;
- 英文论文关键词：Temporal Network ; Time Window Graph Model ; K-shell Decomposition ; Robustness
- 会议召开时间：2017-07-26
- 会议录名称：第36届中国控制会议论文集（A）
- 英文会议录名称：Proceedings of the 36th Chinese Control Conference（A）
- 语种：英文
- 分类号：O157.5
- 学会代码：KZLL
- 会议名称：第36届中国控制会议
- 会议地点：中国辽宁大连
- 主办单位：中国自动化学会控制理论专业委员会
- 学会名称：中国自动化学会控制理论专业委员会
- 页数：6
- 文件大小：566k
- 原文格式：D
- 会议级别：全国
摘要
There is an ever-increasing interest in studying temporal networks nowadays, as temporal networks can illustrate the real-world system more accurately. To date, how to characterize nodes' importance is still unclear in temporal networks. In this work, we first use a time window graph model to cut the temporal network into slices, and then we give an indicator for network centrality according to the edge-based k-shell decomposition for the temporal networks, which is named as temporal k-shell decomposition. We mainly use the size of the largest component after removing the nodes with large centrality value to test the method's performance. The numerical experiments on several real networks indicate that the temporal k-shell method outperforms some other indicators, and the results with different time window size show that the improvement is also robust.
There is an ever-increasing interest in studying temporal networks nowadays, as temporal networks can illustrate the real-world system more accurately. To date, how to characterize nodes' importance is still unclear in temporal networks. In this work, we first use a time window graph model to cut the temporal network into slices, and then we give an indicator for network centrality according to the edge-based k-shell decomposition for the temporal networks, which is named as temporal k-shell decomposition. We mainly use the size of the largest component after removing the nodes with large centrality value to test the method's performance. The numerical experiments on several real networks indicate that the temporal k-shell method outperforms some other indicators, and the results with different time window size show that the improvement is also robust.
There is an ever-increasing interest in studying temporal networks nowadays, as temporal networks can illustrate the real-world system more accurately. To date, how to characterize nodes' importance is still unclear in temporal networks. In this work, we first use a time window graph model to cut the temporal network into slices, and then we give an indicator for network centrality according to the edge-based k-shell decomposition for the temporal networks, which is named as temporal k-shell decomposition. We mainly use the size of the largest component after removing the nodes with large centrality value to test the method's performance. The numerical experiments on several real networks indicate that the temporal k-shell method outperforms some other indicators, and the results with different time window size show that the improvement is also robust.
引文
[1]R.Albert,and A.-L.Barab′asi,Statistical mechanics of complex networks,Reviews of Modern Physics,2002,74(1):47.
[2]P.Holme,and J.Saram¨aki,Temporal networks,Physics Reports,2012,519(3):97-125.
[3]R.Pastor-Satorras,and A.Vespignani,Immunization of complex networks,Physical Review E,2002,65(3),036104.
[4]T.Opsahl,and P.Panzarasa,Clustering in weighted networks,Social Networks,2009,31(2):155-163.
[5]X.REN,and L.Lü,Review of ranking nodes in complex networks,Chinese Science Bulletin,2014,59(13):1175-1197.
[6]H.Kim,and R.Anderson,Temporal node centrality in complex networks,Physical Review E,2012,85(2):026107.
[7]T.Takaguchi,N.Sato,K.Yano,and N.Masuda,Importance of individual events in temporal networks,New Journal of Physics,2012,14(9):093003.
[8]D.Taylor,S.Myers,A.Clauset,and P.Mucha,Eigenvectorbased centrality measures for temporal networks,ar Xiv preprint ar Xiv:1507.01266,2015.
[9]E.Costa,A.Vieira,K.Wehmuth,A.Ziviani,and A.DA Silva,Time centrality in dynamic complex networks,Advances in Complex Systems,2015,18(07n08):1550023.
[10]M.Kitsak,L.Gallos,S.Havlin,F.Liljeros,L.Muchnik,H.Stanley,and H.Makse,Identification of influential spreaders in complex networks,Nature Physics,2010,6(11):888-893.
[11]Y.Liu,M.Tang,T.Zhou,and Y.Do,Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition,Scientific Reports,2015,5.
[12]S.Pei,L.Muchnik,Jr.Andrade,Z.Zheng,and H.Makse,Searching for superspreaders of information in real-world social media,Scientific Reports,2014,4.
[13]G.Krings,M.Karsai,S.Bernhardsson,V.Blondel,and J.Saram¨aki,Effects of time window size and placement on the structure of an aggregated communication network,EPJ Data Science,2012,1(1):1.
[14]M.Génois,C.Vestergaard,J.Fournet,A.Panisson,I.Bonmarin,and A.Barrat,Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers,Network Science,2015,3(03):326-347.
[15]C.Schneider,A.Moreira,Jr.Andrade,S.Havlin,and H.Herrmann,Mitigation of malicious attacks on networks,Proceedings of the National Academy of Sciences USA,2011,108(10):3838-3841.
[16]S.Iyer,T.Killingback,B.Sundaram,and Z.Wang,Attack robustness and centrality of complex networks,PLo S ONE,2013,8(4):e59613.
[17]D.Callaway,M.Newman,S.Strogatz,and D.Watts,Network robustness and fragility:Percolation on random graphs.Physical Review Letters,2000,85(25):5468.
[18]R.Mastrandrea,J.Fournet,and A.Barrat,Contact patterns in a high school:a comparison between data collected using wearable sensors,contact diaries and friendship surveys,PLo S ONE,2015,10(9):e0136497.
[19]L.Isella,J.Stehlé,A.Barrat,C.Cattuto,J.Pinton,and W.Van den Broeck,What’s in a crowd?Analysis of faceto-face behavioral networks,Journal of Theoretical Biology,2011,271(1):166-180.
[20]R.Michalski,S.Palus,and P.Kazienko,Matching organizational structure and social network extracted from email communication,International Conference on Business Information Systems,Springer Berlin Heidelberg,2011:197-206.
[21]Z.-K.Zhang,C.Liu,X.-X.Zhan,X.Lu,C.-X.Zhang,and Y.-C.Zhang,Dynamics of informaion diffusion and its applications on complex networks,Physics Reports,2016,651:1-34.
[2]P.Holme,and J.Saram¨aki,Temporal networks,Physics Reports,2012,519(3):97-125.
[3]R.Pastor-Satorras,and A.Vespignani,Immunization of complex networks,Physical Review E,2002,65(3),036104.
[4]T.Opsahl,and P.Panzarasa,Clustering in weighted networks,Social Networks,2009,31(2):155-163.
[5]X.REN,and L.Lü,Review of ranking nodes in complex networks,Chinese Science Bulletin,2014,59(13):1175-1197.
[6]H.Kim,and R.Anderson,Temporal node centrality in complex networks,Physical Review E,2012,85(2):026107.
[7]T.Takaguchi,N.Sato,K.Yano,and N.Masuda,Importance of individual events in temporal networks,New Journal of Physics,2012,14(9):093003.
[8]D.Taylor,S.Myers,A.Clauset,and P.Mucha,Eigenvectorbased centrality measures for temporal networks,ar Xiv preprint ar Xiv:1507.01266,2015.
[9]E.Costa,A.Vieira,K.Wehmuth,A.Ziviani,and A.DA Silva,Time centrality in dynamic complex networks,Advances in Complex Systems,2015,18(07n08):1550023.
[10]M.Kitsak,L.Gallos,S.Havlin,F.Liljeros,L.Muchnik,H.Stanley,and H.Makse,Identification of influential spreaders in complex networks,Nature Physics,2010,6(11):888-893.
[11]Y.Liu,M.Tang,T.Zhou,and Y.Do,Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition,Scientific Reports,2015,5.
[12]S.Pei,L.Muchnik,Jr.Andrade,Z.Zheng,and H.Makse,Searching for superspreaders of information in real-world social media,Scientific Reports,2014,4.
[13]G.Krings,M.Karsai,S.Bernhardsson,V.Blondel,and J.Saram¨aki,Effects of time window size and placement on the structure of an aggregated communication network,EPJ Data Science,2012,1(1):1.
[14]M.Génois,C.Vestergaard,J.Fournet,A.Panisson,I.Bonmarin,and A.Barrat,Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers,Network Science,2015,3(03):326-347.
[15]C.Schneider,A.Moreira,Jr.Andrade,S.Havlin,and H.Herrmann,Mitigation of malicious attacks on networks,Proceedings of the National Academy of Sciences USA,2011,108(10):3838-3841.
[16]S.Iyer,T.Killingback,B.Sundaram,and Z.Wang,Attack robustness and centrality of complex networks,PLo S ONE,2013,8(4):e59613.
[17]D.Callaway,M.Newman,S.Strogatz,and D.Watts,Network robustness and fragility:Percolation on random graphs.Physical Review Letters,2000,85(25):5468.
[18]R.Mastrandrea,J.Fournet,and A.Barrat,Contact patterns in a high school:a comparison between data collected using wearable sensors,contact diaries and friendship surveys,PLo S ONE,2015,10(9):e0136497.
[19]L.Isella,J.Stehlé,A.Barrat,C.Cattuto,J.Pinton,and W.Van den Broeck,What’s in a crowd?Analysis of faceto-face behavioral networks,Journal of Theoretical Biology,2011,271(1):166-180.
[20]R.Michalski,S.Palus,and P.Kazienko,Matching organizational structure and social network extracted from email communication,International Conference on Business Information Systems,Springer Berlin Heidelberg,2011:197-206.
[21]Z.-K.Zhang,C.Liu,X.-X.Zhan,X.Lu,C.-X.Zhang,and Y.-C.Zhang,Dynamics of informaion diffusion and its applications on complex networks,Physics Reports,2016,651:1-34.