基于社团结构的结构洞占据者发现方法研究

发布时间：2018-03-07 07:46

本文选题：结构洞　切入点：社团结构　出处：《安徽大学》2017年硕士论文　论文类型：学位论文

【摘要】：结构洞是现实网络中普遍存在的现象,伯特的结构洞理论指出在社会结构中占据结构洞位置的个体或企业,可以获得更多的职业机会或竞争优势。在信息网络中,占据结构洞位置的个体能够从不同团体中获得更关键的信息和资源,从而影响网络中的信息传播和个体间的成员关系。在社会学领域,结构洞是非冗余联系人之间的缺口,在不同个体或团体间起到中介作用。个体或者团体间的中间人可以获得丰富的信息并控制他们的网络关系,在网络中占据桥接位置的个体可以获得丰厚的利益。结构洞在获取网络有效信息方面起着关键的作用,且发现网络中的结构洞可以对网络结构进行优化并增强鲁棒性。结构洞理论作为网络结构分析的重要方法,在不同领域和学科的研究中都获得了丰富的成果。已有研究表明现实网络除了具有小世界和无标度的特性外,还具有社团结构的特征。网络中的信息从一个社团传播到其他社团,跨越不同社团可以获得非冗余信息。结构洞占据者拥有从多个社团获取信息和资源的潜力,并在社团间的信息传播过程中起中介作用。社团结构对结构洞研究具有重要的意义和作用,现有的结构洞发现方法主要考虑的是网络拓扑。基于社团结构的结构洞发现方法主要考虑结构洞在不同团体间信息传播过程中的作用,而较少考虑到社团间的中介位置和节点的社团特征,如忽略节点连接的社团数量和规模对节点跨越结构洞的影响。本文研究重点在于如何结合社团结构发现网络中的结构温占据者。首先结合多粒度思想与社团结构,发现不同粒度下网络划分的社团结构也会不同,即社团结构具有层次化的特点,粗粒度下的社团在细粒度下可能划分为多个社团。不同粒度下网络中的结构洞位置也会不同,并且影响节点跨越结构洞的程度,因此结合多粒度与社团结构可以更加准确的发现不同粒度下网络中的结构洞占据者。基于这种思想,本文提出基于社团结构的多粒度结构洞占据者发现方法MG_MaxD。然后通过利用网络拓扑和社团内部结构对影响节点跨越结构洞的因素进行分析并提出两个定义,即邻居重要性和社团影响力。通过分析发现节点的社团特征可以用来衡量节点跨越结构洞的程度并由此提出新的结构洞衡量指标。基于对结构洞占据者在网络中的的桥接属性和传播能力分析,本文提出基于网络拓扑和社团内部结构的结构洞占据者发现方法NTCIS。本文主要围绕发现网络中的结构洞占据者进行展开,主要工作具体如下:(1)分析了常用的结构洞占据者衡量指标,如约束度、介数中心性、PageRank等方法。将结构洞占据者的发现方法归纳为两类,分别从网络拓扑和社团结构两方面来总结现有的结构洞发现方法。在结构洞的实际应用中,探讨了将结构洞理论应用到其他研究中。(2)针对社团结构具有层次化特点,不同粒度下节点跨越结构洞程度会发生变化的问题。基于已有的结构洞发现方法,提出在多粒度社团结构中的结构洞发现方法MG_MaxD。该算法不仅考虑到了网络具有社团结构的重要特征,而且将多粒度思想与社团划分结合,可以有效的发现在不同粒度层次下网络中的结构洞占据者。在公用和真实数据集上的实验验证了算法的可行性,并与另一种重要方法进行对比。最后有效的验证了本文提出的算法能够发现节点在不同粒度层次下跨越结构洞的程度会发生变化。(3)针对现有的结构洞占据者发现方法大部分基于网络拓扑,而对社团内部结构研究较少的问题。首先利用网络拓扑和社团内部结构分别提出两个新的定义,即邻居重要性和社团影响力。并根据社团结构中节点具有的社团特征提出新的结构洞度量指标。最后提出基于网络拓扑和社团内部结构的结构洞占据者发现算法NTCIS。实验结果表明,NTCIS算法可以准确发现网络中的结构洞占据者,并且这些节点桥接着更多和更大的社团,在不同个体间发挥更重要的中介作用。
[Abstract]:The structure of hole is a ubiquitous phenomenon in the network, Bert pointed out that the structural hole theory's structure hole position of individuals or companies in the social structure, can obtain more opportunities for occupation or competitive advantage. In the information network, occupy the location of the hole structure of individual can obtain more key information and resources from different groups. Which affect the network information dissemination and between individual members. In the field of sociology, the structure of hole is between the non redundant contact gap plays an intermediary role in different individuals or groups. In between individuals or groups can obtain abundant information and control their networks, occupy the position of the bridge individuals in the network can get huge benefits. The hole structure plays a key role in acquiring effective information network, and find the structural holes in the network can carry on network structure Optimization and robustness. An important method to analyze the structural hole theory as the structure of the network in various fields and disciplines have gained abundant achievements. Studies have shown that the real network has the characteristics of small world and scale-free, also has the characteristics of community structure. In the network information dissemination from a society to other societies, across different societies can get non redundant information. The hole structure has occupied access to information and resources in many societies and the potential of the information dissemination process in the community plays an intermediary role. The community structure has important significance and role of structural hole research, structural holes found in existing methods mainly consider is the network topology structure. The hole based on community structure discovery methods mainly consider the role of structural holes in different groups in the process of information transmission, and less consideration to the intermediary between communities Community characteristics of location and nodes, such as neglecting the effect of the number and size of community connections of nodes across structural holes. This paper focuses on how to combine the community structure found in the network structure temperature occupy. First combining with the multi granularity thought and community structure, finding community structure in different granularities of network division also have different characteristics the community has the hierarchical structure, coarse grain under the community may be divided into a number of associations in the fine-grained structure. The hole under different granularity in the network will be different, and the influence of the degree of structural holes across nodes, thus combining multi granularity and community structure can more accurately find the hole structure under different granularity in the network occupied. Based on this idea, this paper proposes a multiple granularity structure hole community structure discovery method occupy MG_MaxD. and then through the use of network topology and community based on The factors influence on internal structure nodes across structural holes is analyzed and proposed two definitions, namely the importance of neighbor and community influence. Through the analysis of community characteristics of the node can be used to measure the degree of hole structure across the nodes and thus put forward the new measure. The hole structure analysis in the network and communication ability based on the bridging properties occupied the structure of hole, this hole structure of the internal structure of the network topology and the community occupy NTCIS. detection methods in this thesis found that structural holes in the network are occupied based on specific, main work are as follows: (1) analysis of the structural hole commonly occupy measure, such as beam degree, betweenness centrality PageRank, etc. will occupy the structural hole discovery method is divided into two categories, found the method respectively from the two aspects of network topology and community structure to summarize the existing structural holes. The actual application in structural holes, discusses the structural hole theory is applied to other research. (2) according to the community structure has the characteristics of hierarchy, different size of nodes across the structural holes of the degree of change. The problem of discovery method based on the existing structural holes, proposes the structure hole in the multi granularity in the community structure an important feature of the MG_MaxD. algorithm found method not only takes into account the network with community structure, and combining the multi granularity thought and divided societies, can effectively find out structural holes at different levels of granularity in network occupy. In public and experiments on real data sets to verify the feasibility of the algorithm, and compared with the other one of the important methods. Finally, verified the proposed algorithm can find nodes across structural holes at different levels of granularity of the degree of change. (3) according to the structure of the existing hole for According to the researchers found that most of the methods based on the network topology, and to study the internal structure of less association. Firstly, the internal structure of the network topology and the community are put forward two new concepts, namely the importance of neighbors and community influence. And put forward the new structure according to the characteristics of the node Association hole in the community structure with metrics. Finally, structural holes the internal structure of the network topology and the community occupy discovery algorithm NTCIS. based on the experimental results, the NTCIS algorithm can accurately find the structural holes in the network to occupy, and then these nodes bridge more and more clubs play an intermediary role is more important among different individuals.

【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】