基于主成分分析的网络节点重要性指标贡献评价
|
摘要
为研究不同网络节点重要性指标对网络中重要节点的影响程度,进而优选出较能体现网络重要节点性质的指标.本文基于主成分分析(Principal Component Analysis,简记PCA),选取七个节点重要性指标对网络重要性节点贡献率进行计算分析,同时选取了七种不同的网络进行实验,得到指标贡献率大小顺序,利用肯德尔系数对重要指标与其余指标进行相关性分析,得到不同指标之间的相关系数及相关系数大小的影响因素.本文为研究网络重要节点选择指标提供了一种思路,同时为研究不同节点间的相互关系提供了研究方法.
In network theory, it is interest to study the influences of different nodes on the key nodes in the network,and build or select the proper node importance index to model it. This paper selects seven node importance indices to calculate and analyze their contributions in nodes' importance evaluation with Principal Component Analysis. Seven empirical networks are used for experiments. Moreover, the order of different contributions of indices is obtained, and the correlation analysis between the most important index and the other indices is carried out using the Kendall coefficient, and factors affecting the correlation coefficient are also discussed. This paper provides a way to select the node importance index in the network,and the results could also be used for studying the relationships between different nodes.
In network theory, it is interest to study the influences of different nodes on the key nodes in the network,and build or select the proper node importance index to model it. This paper selects seven node importance indices to calculate and analyze their contributions in nodes' importance evaluation with Principal Component Analysis. Seven empirical networks are used for experiments. Moreover, the order of different contributions of indices is obtained, and the correlation analysis between the most important index and the other indices is carried out using the Kendall coefficient, and factors affecting the correlation coefficient are also discussed. This paper provides a way to select the node importance index in the network,and the results could also be used for studying the relationships between different nodes.
引文
[1] Bonacich P. Factoring and weighting approaches to statusscores and clique identification[J]. Journal of M athemati-cal Sociology,1972,2(1):113-120.
[2]Freeman L C. A set of measures of centrality based on be-tw eenness[J]. Sociometry,1977,40(1):35-41.
[3]Freeman L C. Centrality in social networks conceptual clar-ification[J]. Social Netw orks,1979,1(3):215-239.
[4]Kleinberg J M. Authoritative sources in a hyperlinked envi-ronment[J]. Journal of Acm,1999,46(5):604-632.
[5]Qi X,Duval R D,Christensen K,et al. Terrorist networks,netw ork energy and node removal:a new measure of cen-trality based on laplacian energy[J]. Social Netw orking,2013,2(1):19-31.
[6]Burt R S. Structural Holes:The Social Structure of Compe-tition[M]. Harvard University Press,2010.
[7] Chen D B,LüL,Shang M S,et al. Identifying influentialnodes in complex netw orks[J]. Physica A Statistical M e-chanics&Its Applications,2012,391(1):1777-1787.
[8] Phillip Bonacich. Factoring and weighting approaches tostatus scores and clique identification[J]. Journal of M ath-ematical Sociology,1972,2(1):113-120.
[9]Dangalchev C. Residual closeness in networks[J]. PhysicaA Statistical M echanics&Its Applications,2006,365(2):556-564.
[10]Kitsak M,Gallos L K,Havlin S,et al. Identification of in-fluential spreaders in complex netw orks[J]. Nature Phys-ics,2011,6(11):888-893.
[11]Brin S,Page L. The anatomy of a large-scale hypertextualWeb search engine[A]. International Conference onWorld Wide Web[C]. Elsevier Science Publishers B. V.1998. 107-117.
[12] Poulin R,Boily M C,Msse B R. Dynamical systems todefine centrality in social netw orks[J]. Social Netw orks,2000,22(3):187-220.
[13]Linyuan L,Zhang Y C,Ho Y C,et al. Leaders in socialnetw orks,the delicious case[J]. Plos One,2011,6(6):e21202.
[14]汪应洛.系统工程.第5版[M].北京:机械工业出版社,2015. 52-55.Wang Ying-luo. Systems Engineering. Fifth Edition[M].Beijing:China M achine Press,2015. 52-55.(in Chi-nese)
[15]汪小帆,李翔,陈关荣.网络科学导论[M].北京:高等教育出版社,2012. 161-162.Wang Xiao-fan,Li Xiang,Chen Guan-rong. An Introduc-tion of Netw ork Science[M]. Beijing:Higher EducationPress,2012. 161-162.(in Chinese)
[16] Klovdahl A S. Social networks and the spread of infec-tious diseases:the AIDS example[J]. Social Science&M edicine,1985,21(11):1203-1216.
[17]刘忠华,于华,杨方廷.基于复杂网络理论的水网节点重要性评价研究[J].中国科学:技术科学,2014(12):1280-1294.Liu Zhong-hua,Yu Hua,Yang Fang-ting. Evaluate thenode importance for w ater netw ork based on complex net-w ork theory[J]. Chinese Science:Technical Science,2014(12):1280-1294.(in Chinese)
[18]王政,孙锦程,刘晓强,等.基于复杂网络理论的大型换热网络节点重要性评价[J].化工进展,2017,36(5):1581-1588.Wang Zheng,Sun Jin-cheng,Liu Xiao-qiang,Jiang Ying,Jia Xiaoping,Wang Fang. Evaluation of the node impor-tance for large heat exchanger netw ork based on complexnetw ork theory[J]. Chemical Industry and EngineeringProgress,2017,36(5):1581-1588.(in Chinese)
[19]韩忠明,吴杨,谭旭升,等.面向结构洞的复杂网络关键节点排序[J].物理学报,2015,64(5):421-429.Han Zhong-ming,Wu Yang,Tan Xu-sheng,Duan Da-gao,Yang Wei-jie. Ranking key nodes in complex net-w orks by considering structural holes[J]. Acta PhysicaSinica,2015,64(5):421-429.(in Chinese)
[20]苏晓萍,宋玉蓉.利用邻域“结构洞”寻找社会网络中最具影响力节点[J].物理学报,2015,64(2):1-11.Su Xiao-ping,Song Yu-rong. Leveraging neighborhood“structural holes”to identifying key spreaders in socialnetw orks[J]. Acta Physica Sinica,2015,64(2):1-11.(in Chinese)
[21]Yu H,Cao X,Liu Z,et al. Identifying key nodes based onimproved structural holes in complex netw orks[J]. Physi-ca A Statistical M echanics&Its Applications,2017,486.
[22]于会,刘尊,李勇军.基于多属性决策的复杂网络节点重要性综合评价方法[J].物理学报,2013,62(2):020204-1-020204-9.Yu Hui,Liu Zun,Li Yong-jun. Key nodes in complex net-w orks identified by multi-attribute decision-making meth-od[J]. Acta Physica Sinica,2013,62(2):020204-1-020204-9.(in Chinese)
[23]Zhang K,Zhang H,Wu Y D,et al. Evaluating the impor-tance of nodes in complex netw orks based on principalcomponent analysis and grey relational analysis[A]. IEEEInternational Conference on Netw orks[C]. 2011. 6955(2):231-235.
[24] Kendall M G. The treatment of ties in ranking problems[J]. Biometrika,1945,33(3):239-251.
[2]Freeman L C. A set of measures of centrality based on be-tw eenness[J]. Sociometry,1977,40(1):35-41.
[3]Freeman L C. Centrality in social networks conceptual clar-ification[J]. Social Netw orks,1979,1(3):215-239.
[4]Kleinberg J M. Authoritative sources in a hyperlinked envi-ronment[J]. Journal of Acm,1999,46(5):604-632.
[5]Qi X,Duval R D,Christensen K,et al. Terrorist networks,netw ork energy and node removal:a new measure of cen-trality based on laplacian energy[J]. Social Netw orking,2013,2(1):19-31.
[6]Burt R S. Structural Holes:The Social Structure of Compe-tition[M]. Harvard University Press,2010.
[7] Chen D B,LüL,Shang M S,et al. Identifying influentialnodes in complex netw orks[J]. Physica A Statistical M e-chanics&Its Applications,2012,391(1):1777-1787.
[8] Phillip Bonacich. Factoring and weighting approaches tostatus scores and clique identification[J]. Journal of M ath-ematical Sociology,1972,2(1):113-120.
[9]Dangalchev C. Residual closeness in networks[J]. PhysicaA Statistical M echanics&Its Applications,2006,365(2):556-564.
[10]Kitsak M,Gallos L K,Havlin S,et al. Identification of in-fluential spreaders in complex netw orks[J]. Nature Phys-ics,2011,6(11):888-893.
[11]Brin S,Page L. The anatomy of a large-scale hypertextualWeb search engine[A]. International Conference onWorld Wide Web[C]. Elsevier Science Publishers B. V.1998. 107-117.
[12] Poulin R,Boily M C,Msse B R. Dynamical systems todefine centrality in social netw orks[J]. Social Netw orks,2000,22(3):187-220.
[13]Linyuan L,Zhang Y C,Ho Y C,et al. Leaders in socialnetw orks,the delicious case[J]. Plos One,2011,6(6):e21202.
[14]汪应洛.系统工程.第5版[M].北京:机械工业出版社,2015. 52-55.Wang Ying-luo. Systems Engineering. Fifth Edition[M].Beijing:China M achine Press,2015. 52-55.(in Chi-nese)
[15]汪小帆,李翔,陈关荣.网络科学导论[M].北京:高等教育出版社,2012. 161-162.Wang Xiao-fan,Li Xiang,Chen Guan-rong. An Introduc-tion of Netw ork Science[M]. Beijing:Higher EducationPress,2012. 161-162.(in Chinese)
[16] Klovdahl A S. Social networks and the spread of infec-tious diseases:the AIDS example[J]. Social Science&M edicine,1985,21(11):1203-1216.
[17]刘忠华,于华,杨方廷.基于复杂网络理论的水网节点重要性评价研究[J].中国科学:技术科学,2014(12):1280-1294.Liu Zhong-hua,Yu Hua,Yang Fang-ting. Evaluate thenode importance for w ater netw ork based on complex net-w ork theory[J]. Chinese Science:Technical Science,2014(12):1280-1294.(in Chinese)
[18]王政,孙锦程,刘晓强,等.基于复杂网络理论的大型换热网络节点重要性评价[J].化工进展,2017,36(5):1581-1588.Wang Zheng,Sun Jin-cheng,Liu Xiao-qiang,Jiang Ying,Jia Xiaoping,Wang Fang. Evaluation of the node impor-tance for large heat exchanger netw ork based on complexnetw ork theory[J]. Chemical Industry and EngineeringProgress,2017,36(5):1581-1588.(in Chinese)
[19]韩忠明,吴杨,谭旭升,等.面向结构洞的复杂网络关键节点排序[J].物理学报,2015,64(5):421-429.Han Zhong-ming,Wu Yang,Tan Xu-sheng,Duan Da-gao,Yang Wei-jie. Ranking key nodes in complex net-w orks by considering structural holes[J]. Acta PhysicaSinica,2015,64(5):421-429.(in Chinese)
[20]苏晓萍,宋玉蓉.利用邻域“结构洞”寻找社会网络中最具影响力节点[J].物理学报,2015,64(2):1-11.Su Xiao-ping,Song Yu-rong. Leveraging neighborhood“structural holes”to identifying key spreaders in socialnetw orks[J]. Acta Physica Sinica,2015,64(2):1-11.(in Chinese)
[21]Yu H,Cao X,Liu Z,et al. Identifying key nodes based onimproved structural holes in complex netw orks[J]. Physi-ca A Statistical M echanics&Its Applications,2017,486.
[22]于会,刘尊,李勇军.基于多属性决策的复杂网络节点重要性综合评价方法[J].物理学报,2013,62(2):020204-1-020204-9.Yu Hui,Liu Zun,Li Yong-jun. Key nodes in complex net-w orks identified by multi-attribute decision-making meth-od[J]. Acta Physica Sinica,2013,62(2):020204-1-020204-9.(in Chinese)
[23]Zhang K,Zhang H,Wu Y D,et al. Evaluating the impor-tance of nodes in complex netw orks based on principalcomponent analysis and grey relational analysis[A]. IEEEInternational Conference on Netw orks[C]. 2011. 6955(2):231-235.
[24] Kendall M G. The treatment of ties in ranking problems[J]. Biometrika,1945,33(3):239-251.