The Calculation of Connected Dominating Centrality in Complex Network
XU Minzheng1,2, XU Jun1, CHEN Yu1
1. Institute of Geographic Sciences and Natural Resources Research, Chinese Academy of Sciences, Beijing 100101, China; 2. College of Resources and Environment, University of Chinese Academy of Sciences, Beijing 100049, China
Abstract：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.
