分析了现实生活中对重要节点的需求背景,对连通的网络模型提出了一种新型中心性评价指标,连通支配中心性。该中心性利用网络连通支配集的“连通”和“支配”两大特性,通过循环构建点导出支配子图的连通支配集,生成一棵支配关系扩展有向树。然后基于各节点在该有向树中的支配层次数,支配数和支配边权值3方面的属性,设计了反映节点支配能力强弱的中心性计算公式。最后以合作关系图为例进行相应实验,发现连通支配中心性比较高的节点不仅构成了网络的骨干网,能较好地维持网络基本形态,而且能桥接几个不同研究分区,起到一定的中介作用,体现了网络中节点的组织控制能力。
In this paper, we propose a novel centrality called connected dominating centrality according to the real-life demand analysis. The connected dominating set of a network has two characteristics, connectivity and dominance. Based on the two characteristics, we recursively construct the connected dominating sets of the induced dominating sub graphs and generate a directed spanning tree with dominating relationships. By combining the number of nodes dominated by a node, its hierarchical level in the directed spanning tree, and the weights of the edges which connect the dominator and its dominated nodes, we define the calculation formula of our proposed connected dominating centrality. To verify the effectiveness of the centrality, an experiment is made on the paper co-author network of an international journal. The experimental results show that the nodes with higher connected dominating centrality constitute the backbone network and can maintain the shape of network well. Some of them bridge different research communities; others are the kernels of communities. They have good ability in organizing and controlling the network.
[1] Albert R, Barabási A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002,74（1):47.
[2] Howe D, Costanzo M, Fey P, et al. Big data:the future of biocuration[J]. Nature. 2008, 455（7209):47-50.
[3] Albert R, Jeong H, Barabási A L. Error and attack tolerance of complex networks[J]. Nature, 2000, 406（6794):378-82.
[4] Gallos L K, Cohen R, Argyrakis P, et al. Stability and topology of scale-free networks under attack and defense strategies[J]. Physical Review Letters, 2005, 94（18):188701.
[5] 赫南, 李德毅, 淦文燕, 等. 复杂网络中重要性节点发掘综述[J]. 计算机科学, 2007, （12):1-5.
He Nan, Li Deyi, Gan Wenyan, et al. Mining Vital Nodes in Complex Networks[J]. Computer science. 2007（12):1-5.
[6] Shetty J, Adibi J. Discovering important nodes through graph entropy the case of enron email database[C]// Proceedings of the 3rd International Workshop on Link Discovery. Chicago:ACM, 2005:74-81.
[7] Freeman L C. Centrality in social networks conceptual clarification[J]. Social Networks, 1979,1（3):215-39.
[8] Bonacich P. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology, 1972,2（1):113-120.
[9] Bonacich P. Power and centrality:a family of measures[J]. American Journal of Sociology. 1987:1170-1182.
[10] Freeman L C, Borgatti S P, White D R. Centrality in valued graphs:a measure of betweenness based on network flow[J]. Social Networks, 1991,13（2):141-54.
[11] Tutzauer F. Entropy as a measure of centrality in networks characterized by path-transfer flow[J]. Social Networks. 2007, 29（2):249-65.
[12] Wu J, Dai F, Gao M, et al. On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks[J]. Journal of Communications and Networks and Networks, 2002, 4（1):59-70.
[13] 施韦. 移动 Ad Hoc 网络中连通支配集若干关键问题的研究[D]. 浙江:浙江大学, 2007.
Shi Wei. Connected dominating Set in MANETs[D]. Zhejiang:Zhejiang University, 2007.
[14] 张冰燕. Ad Hoc网络中连通支配集算法研究[D]:甘肃:兰州理工大学, 2008.
Zhang Bingyan. Connected dominating set algorithm study in ad hoc networks[D]. Gansu:Lanzhou University of Technology, 2008.
[15] 高随祥. 图论与网络流理论[M]. 北京:高等教育出版社, 2009:132.
[16] Guha S, Khuller S. Approximation algorithms for connected dominating sets[J]. Algorithmica, 1998, 20（4):374-87.
[17] Lu H I, Ravi R. Approximating maximum leaf spanning trees in almost linear time[J]. Journal of Algorithms. 1998,29（1):132-41.
[18] Goodchild M F. Geographical information science[J]. International Journal of Geographical Information Systems, 1992, 6（1):31-45.
[19] Liu Y, Goodchild M F, Guo Q, et al. Towards a general field model and its order in GIS[J]. International Journal of Geographical Information Science. 2008,22（6):623-643.
