计算机工程 ›› 2018, Vol. 44 ›› Issue (5): 174-181,187.doi: 10.19678/j.issn.1000-3428.0048085

• 人工智能及识别技术 • 上一篇    下一篇

基于重要节点删除法的社会网络层次结构分析

王魁,马宏,黄瑞阳   

  1. 国家数字交换系统工程技术研究中心,郑州 450002
  • 收稿日期:2017-07-24 出版日期:2018-05-15 发布日期:2018-05-15
  • 作者简介:王魁(1995—),男,硕士研究生,主研方向为社会网络分析、信息可视化;马宏,研究员;黄瑞阳,副研究员、博士。
  • 基金项目:
    国家自然科学基金(61171108);国家重点基础研究发展计划项目(2012CB315905);国家科技支撑计划项目(2014BAH30B01)。

Hierarchical Structure Analysis of Social Network Hierarchical Structure Analysis of Social Network Based on Important Nodes Removal Method Based on Important Nodes Removal Method

WANG Kui,MA Hong,HUANG Ruiyang   

  1. National Digital Switching System Engineering and Technological Research Center,Zhengzhou 450002,China
  • Received:2017-07-24 Online:2018-05-15 Published:2018-05-15

摘要: 社会网络的结构分析一般通过社团探测来实现,但现实网络中节点具有层次性,少量节点拥有大量连接,使网络不能得到最优划分。为此,提出一种改进的基于重要节点删除的网络分解方法。运用基于中心节点删除的网络分解策略对复杂网络结构进行分析,通过节点介数的快速计算方法计算节点中心性,以迭代的方式删除中心节点使网络分解,并将中心节点与分解出的分支在邻接矩阵中的位置重排序,得出社会网络的层次结构划分。在真实网络上的实验结果表明,删除网络中介数最高的节点可使网络快速分解,根据网络分解结果将原网络简化为一个以中心节点为核心,以分解出的较大分支为叶子的星型结构,可以更好地表示网络中节点的层次关系。

关键词: 社会网络, 网络分解, 层次结构, 邻接矩阵, 重排序

Abstract: The structure analysis of social networks is generally implemented through the detection of communities,but the nodes in the real network are hierarchical,a small number of nodes have a large number of connections,so that the network often does not have an optimal division.Therefore,an improved network decompostion method based on removal of important nodes is proposed.The network decomposition strategy based on the removal of the central node is used to analyze the complex network structure,the node centrality is calculated by the fast calculation method of the node involution,the central node is deleted in an iterative manner to decompose the network,and the central node is adjacent to the decomposed branches,the reordering of positions in the matrix yields a hierarchical structure of social networks.Experimental results on a real network show that deleting the node with the highest number of network can quickly decompose the network,according to the network decomposition results,the original network is reduced to a star type with the center node as the core and the decomposed larger branch as leaves as the decomposition,structures can better represent the hierarchical relationships of nodes in the network.

Key words: social network, network decomposition, hierarchical structure, adjacency matrix, reordering

中图分类号: