Hierarchical Structure Discovery in Social Networks
CHENG Qing1, HUANG Sen2, HUANG Jincai1
1. Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha, 410073,China; 2. Unit 78020 of PLA, Kunming 650221, China
Abstract：According to the fact that the conventional social network analysis methods did not consider the role of network property, such as social individuals′ position, the strength of social relations. We introduced a new social network model based on extended graph and hierarchical structure based on information flow. Also, we proposed a method for discovering the backbone nodes based on the Network Topology Potential Support and a method for discovering the network hierarchy based on the potential flow. The experimental results show the effectiveness of our method in mining the hierarchical structure of networks.
[1] Wasserman S, Faust K. Social Network Analysis[M]. Cambridge:Cambridge University Press, 1994. [2] Scot J. Social Network Analysis:A Handbook[M].2nd. London:Sage Publications Ltd, 2000. [3] Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the internet topology[J]. Computer Communication Review,1999, 29:251-262. [4] Pastor-Satorras R, Vespignani A. Evolution and Structure of the Internet[M]. Cambridge: Cambridge University Press, 2004. [5] Barabasi A-L, Oltvai Z N. Network biology: understanding the cell′s functional organization[J]. Nature Reviews Genetics, 2004,5(2):101-113. [6] Barabasi A-L, Gulbahce N, Loscalzo J. Network medicine: a network based approach to human disease[J]. Nature Reviews Genetics, 2011, 12(1):56-68. [7] Lane D. Hierarchy, Complexity, Society[M]. Dodrecht, the Netherlands: Springer, 2006:81-120. [8] Memon N, Larsen H L, Hicks D L, et al. Detecting hidden hierarchy in terrorist networks: Some case studies[C]//Proceedings of the IEEE ISI 2008 PAISI, PACCF, and SOCO international workshops on Intelligence and Security Informatics. Berlin, Heidelberg: Springer-Verlag, 2008:477-489. [9] Seidman S. Network structure and minimum degree[J].Social Networks, 1983, 5: 269-287. [10] Daniel W M. The hierarchical structure of organisms: a scale and documentation of a trend in the maximum[J]. Paleobiology, 2001, 27(2): 405-423. [11] Wimberley E T. Nested ecology. The Place of Humans in the ecological Hierarchy[M]. Baltimore, MD: John Hopkins University Press,2009. [12] Newman M E J. Detecting community structure in networks[J]. European Physical Journal B, 2004, 38(2): 321. [13] Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486:75-174. [14] Newman M E J. Communities, modules and large-scale structure in networks[J]. Nature Physics, 2012,8:25-31. [15] Arun S M, Tanya Y B. Inferring the maximum likelihood hierarchy in social networks[C]//Proceedings of the 2009 International Conference on Computational Science and Engineering. Washington DC: IEEE Computer Society, 2009: 273-283. [16] Mones E, Vicsek L, Vicek T. Hierarchy measure for complex networks[J]. PLoS ONE, 2012, 7(3):e33799. [17] 成清. 社会网络的节点重要度和重叠社区发现研究[D]. 长沙:国防科技大学. 2012. Cheng Qing. Research on node importance evaluation and community discovery in social networks[D]. Changsha: National University of Defense Technology, 2012. [18] 付强,赵小勇. 投影寻踪模型原理及其应用[M]. 北京:科学出版社.2006:47-50. [19] Premchand S N, Suseela T S. Data mining through fuzzy social network analysis[C]//Proceedings of the 26th Annual Meeting of the North American Fuzzy Information Processing Society. San Diego: Institute of Electrical and Electronics Engineers Inc, 2007:251-255. [20] 刘振亚. 面向C2组织效能测度的探索性分析方法研究[D]. 长沙:国防科技大学. 2009. Liu Zhenya. A research of exploratory analysis for measure of C2 organizational effectiveness[D]. Changsha: National University of Defense Technology, 2009. [21] 李德毅,杜鹢. 不确定性人工智能[M]. 北京:国防工业出版社. 2005:197-212. [22] Faloutsos C, McCurley K S, Tomkins A. Fast discovery of connection subgraphs[C].//Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. New York: Association for Computing Machinery, 2004:119-127. [23] Shetty J, Adibi J. The enron email dataset: database schema and brief statistical report[DB/OL].[2013-07-20]. http://www.isi.edu/?adibi/Enron/EnronDatasetReport.pdf [24] Gilbert E. Phrases that signal workplace hierarchy[C]//Proceedings of the ACM 2012 Conference on Computer Supported Cooperative Work. New York: Association for Computing Machinery, 2012:1037-1046.
