《基于社团结构的结构洞占据者发现方法研究-赵晖.pdf》由会员分享，可在线阅读，更多相关《基于社团结构的结构洞占据者发现方法研究-赵晖.pdf（58页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、参缒硕士学位论文密 级：保密期限：基于社团结构的结构洞占据者发现方法研究Research on Detecting Structural Hole SpannersBased on Community Structure学 号姓 名学位类别学科专业(工程瓴域)指导教师完成时间答辩委员会主席签名E14201033国囝工学硕士计算机应用技术2017年2月磐吠万方数据独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究戏果，也不包含为获得安徽大学或其他教育机构的学位或证书而使用过的材
2、料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名： 丧晖 签字日期： 多ol-年s月均日学位论文版权使用授权书本学位论文作者完全了解安徽大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权安徽大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位论文作者签名： 趣埠签字日期： 州7年 月Jc7日导师签名：签字日期：乡磋扣f年5月”日万方数据摘要 JllJIlllllJJJl JJl
3、llllllJIJJJll llllllJJlJIlllljY321 5424结构洞是现实网络中普遍存在的现象，伯特的结构洞理论指出在社会结构中占据结构洞位置的个体或企业，可以获得更多的职业机会或竞争优势。在信息网络中，占据结构洞位置的个体能够从不同团体中获得更关键的信息和资源，从而影响网络中的信息传播和个体间的成员关系。在社会学领域，结构洞是非冗余联系人之间的缺口，在不同个体或团体间起到中介作用。个体或者团体问的中间人可以获得丰富的信息并控制他们的网络关系，在网络中占据桥接位置的个体可以获得丰厚的利益。结构洞在获取网络有效信息方面起着关键的作用，且发现网络中的结构洞可以对网络结构进行优化并增
4、强鲁棒性。结构洞理论作为网络结构分析的重要方法，在不同领域和学科的研究中都获得了丰富的成果。已有研究表明现实网络除了具有小世界和无标度的特性外，还具有社团结构的特征。网络中的信息从一个社团传播到其他社团，跨越不同社团可以获得非冗余信息。结构洞占据者拥有从多个社团获取信息和资源的潜力，并在社团间的信息传播过程中起中介作用。社团结构对结构洞研究具有重要的意义和作用，现有的结构洞发现方法主要考虑的是网络拓扑。基于社团结构的结构洞发现方法主要考虑结构洞在不同团体间信息传播过程中的作用，而较少考虑到社团间的中介位置和节点的社团特征，如忽略节点连接的社团数量和规模对节点跨越结构洞的影响。本文研究重点在于如
5、何结合社团结构发现网络中的结构洞占据者。首先结合多粒度思想与社团结构，发现不同粒度下网络划分的社团结构也会不同，即社团结构具有层次化的特点，粗粒度下的社团在细粒度下可能划分为多个社团。不同粒度下网络中的结构洞位置也会不同，并且影响节点跨越结构洞的程度，因此结合多粒度与社团结构可以更加准确的发现不同粒度下网络中的结构洞占据者。基于这种思想，本文提出基于社团结构的多粒度结构洞占据者发现方法MG MaxD。然后通过利用网络拓扑和社团内部结构对影响节点跨越结构洞的因素进行分析并提出两个定义，即邻居重要性和社团影响力。通过分析发现节点的社团特征可以用来衡量节点跨越结构洞的程度并由此提出新的结构洞衡量指标
6、。基于对结构洞占据者在网络中的的桥接属性和传播能力分析，本文提出基于网络万方数据拓扑和社团内部结构的结构洞占据者发现方法NTCIS。本文主要围绕发现网络中的结构洞占据者进行展开，主要工作具体如下：(1)分析了常用的结构洞占据者衡量指标，如约束度、介数中心性、PageRank等方法。将结构洞占据者的发现方法归纳为两类，分别从网络拓扑和社团结构两方面来总结现有的结构洞发现方法。在结构洞的实际应用中，探讨了将结构洞理论应用到其他研究中。(2)针对社团结构具有层次化特点，不同粒度下节点跨越结构洞程度会发生变化的问题。基于已有的结构洞发现方法，提出在多粒度社团结构中的结构洞发现方法MG MaxD。该算法
7、不仅考虑到了网络具有社团结构的重要特征，而且将多粒度思想与社团划分结合，可以有效的发现在不同粒度层次下网络中的结构洞占据者。在公用和真实数据集上的实验验证了算法的可行性，并与另一种重要方法进行对比。最后有效的验证了本文提出的算法能够发现节点在不同粒度层次下跨越结构洞的程度会发生变化。(3)针对现有的结构洞占据者发现方法大部分基于网络拓扑，而对社团内部结构研究较少的问题。首先利用网络拓扑和社团内部结构分别提出两个新的定义，即邻居重要性和社团影响力。并根据社团结构中节点具有的社团特征提出新的结构洞度量指标。最后提出基于网络拓扑和社团内部结构的结构洞占据者发现算法NTCIS。实验结果表明，NTCIS
8、算法可以准确发现网络中的结构洞占据者，并且这些节点桥接着更多和更大的社团，在不同个体间发挥更重要的中介作用。关键词：结构洞；社团结构；多粒度；网络拓扑；社团内部结构II万方数据AbstractStmctural hole is a ubiquitous phenomenon in real networkBurts structural holetheory points out that individuals or firms that occupy the structural hole position inthe social structure can gain more care
9、er opportunities or competitive advantagesIninformation networks，individuals occupying structural holes can obtain more criticalinformation and resources from different groups，thus affecting the informationpropagation in network and the relationship among individualsIn the field ofsociology，structur
10、al holes are gaps between non-redundant contacts and play anintermediary role between different individuals or groupsIntermediates betweenindividuals or groups Can gain abundant information and control their networkrelationship，and the individual who occupies the bridging position in network Cangain
11、 great benefitsIhe structural hole plays a key role in obtaining the effectiveinformation of the network，and detecting structural hole Can optimize the networkstructure and enhance the robustness of networkAs an important method of networkstructure analysis，structural hole theory has obtained rich a
12、chievements in differentfields and disciplinesPrevious studies show that the real network has the characteristics of communitystructure besides the small world and scalefree characteristicsThe information in thenetwork is transmitted from=one communi啦to others，and the non?redundantinformation can be
13、 obtained by spanning different communitiesStructural holespanners have the potential to obtain information and resources from multiplecommunities，and play an intermediary role in the process of information propagationbetween communitiesThe community structure has important significance and rolefor
14、the research of structural hole，while the existing structural holes detectionmethods mainly considered the network topologyThe community structure basedalgorithms mainly considered the effect of structural holes in the process ofinformation propagation between different communities，with few consider
15、ed theintermediary position between communities and the community characteristics ofUI万方数据nodesSuch asneglected the effect of the quantity and scale of connectedcommunities of nodes spanning structural holesThe focus of this dissertation is how to find structural hole spanners in networksby combinin
16、g community structureFirstly，we combine the multi-granularity withcommunity structure，and find that the community structure in network partition underdifferent granularity would changeThe community has the characteristic ofhierarchical structure，community under the rough granularity may be divided i
17、ntomultiple communities while under thin granularityThe structural hole position underdifferent granularity in the network will be different，and influence the extent of nodespanning the structural holeTherefore，the combination of multi-granularity andcommunity structure Can detect the structural hol
18、e spanners more accurately in thenetwork under different granularityBased on this idea，this dissertation proposed amethod of recognition and analysis of structural hole spanners in multigranularitybased on community structure，named MGMaxDThen，by using the networktopology and the community inner stru
19、cture，the dissertation analyzes the factors thataffect the nodes to span structural hole and puts forward two definitionsThat is，theneighbor importance and the community influenceThrough the analysis，it is foundthat the community characteristics of node can be used to measure the extent of nodesspan
20、ning the structural holes，and then a novel structural hole measurement isproposedBased on the analysis of the bridging property and the propagation abilityof the structural hole spanner in networks，this dissertation proposed a method formining structural hole spanners using the network topology and
21、the community innerstructures，namely NTCISThis dissertation focus on the detection of structural hole spanners in the network，the main work iS as follows：(1)Analyzing the commonly used measurements of structural hole spanners，suchas degree，betweenness centrality and PageRankThe detection methods of
22、structuralhole spanner is classified into two categories，which are summarized in two aspects：the network topology and the community structureApplying the structural holetheory to other researches was discussed in the practical application of structural holeIV万方数据(2)Since the community structure has
23、the characteristics of hierarchical，theextent of nodes spanning the structural hole will change under different granularityBased on the existing structural hole detection method，a new method of structuralhole detection in community structure under multigranularity is proposedThealgorithm not only ta
24、kes into account the important characteristics of communitystructure of network，but also combined the multigranularity with the communitypartitionThus it can effectively find the structural hole spanners in the network underdifferent levels of granularityThe feasibility of the algorithm is verified
25、on bothpublic and real datasets，and compared with another important methodFinally，it isverified that the proposed algorithm can discover the extent of node to span structuralhole will constant change under different granularity(3)Most of the structural hole detection method are based on the networkt
26、opology，while less to research on the community inner structureFirstly，two noveldefinitions are proposed by using network topology and community inner structurerespectively，that is the neighbor importance and the community influenceAccordingto the characteristics of nodes in community structure，a ne
27、w structural holemeasurement is proposedFinally，this dissertation proposed the algorithm for miningstructural hole spanner based on the network topology and the community innerstructure，namely NTCISThe experimental results show that the NTCIS algorithmcan_accurately find the structural holespanners
28、of the network,and these nodes arebridged with more and larger communities，which play a more important intermediaryrole between different individualsKeyword：Structural hole；Community structure；Multi-granularity；Networktopology；Community inner structureV万方数据目录第一章绪论。111研究背景与意义一112国内外研究现状一313本文主要内容及章节安
29、排一5第二章结构洞理论及相关算法721结构洞理论一7211结构洞定义7212结构洞相关指标822结构洞占据者的相关发现方法9221基于网络拓扑的结构洞占据者发现方法简介9222基于社团结构的结构洞占据者发现方法简介1023本章小结12第三章基于社团结构的多粒度结构洞占据者发现及分析1331 MaxD模型相关介绍一1332层次结构网络结构洞发现方法MG MaxD1433实验设置及结果分析1 6331数据及衡量指标一16332 MG MaxD实验结果分析1 7333 HIS对比实验结果分析19334社团划分质量及社团数的影响2l34本章小结23第四章基于网络拓扑和社团内部结构的结构洞占据者发现方法
30、2441基本定义2442基于节点社团特征的结构洞衡量指标2543基于网络拓扑和社团内部结构的NTCIS算法一2844实验设置及结果分析3 1441实验设置一3 1vI万方数据442社团指标结果分析3244-3平均距离指标结果分析33444调参结果分析3445本章小结35第五章总结与展望3751本文总结3752未来展望38参考文献40附录A图索引44Appendix A Figure Index45附录B表索引46Appendix B Table Index47致谢48攻读硕士期间参与的科研成果49I万方数据第一章绪论11研究背景与意义第章绪论结构洞是美国社会学家罗纳德伯特在1992年根据社交网
31、络中节点之间具有的结构化的关系所提出的概念。伯特的结构自主性研究、Granovetter的求职研究和Cook的网络交换论研究等构成了结构洞理论的基础。社会学领域中的许多研究成果推进了结构洞理论【l】的形成，如Freeman提出的中介中一t3性、Granovetter提出的弱关系强度理论、Cook等人对独家交流伙伴可获取权力的研究和伯特关于网络中的结构自主性的理论。跨越结构洞的个体可能得到网络中更多的信息和控制优势，在社会生活和竞争中具有潜力获得更多的信息和资源。社会学家研究了占据结构洞的企业具有的竞争优势，发现桥接两个关系间断的合作伙伴的团队可以聚集更多的资源；并且占据结构洞的个体可以竞争到更
32、多的职业优势。结构洞可以为占据者带来社会资本，也引起了不同领域的学者对结构洞研究的兴趣。随着参与社会网络的个体增加，社会网络对于人们的重要性也随之增加，使得对社会网络的研究具有更深远的意义。研究者对于社会网络的性质分析逐渐从对网络结构特征分析，如发现网络的拓扑性质含有无标度、小世界特性和社团结构12-61等，转移到对网络中重要节点的发现及分析，如结构洞【11、意见领袖等。在个体或团体间的起中介作用的人可以获得丰富的信息，并对他们的网络关系具有更多的控制，在网络中占据桥接位置的个体可以获得丰厚的利益。结构洞在获取网络有效信息方面起着关键的作用，发现网络中的结构洞可以对网络结构进行优化和增强鲁棒性
33、。结构洞理论作为网络结构分析的重要方法，在不同领域和学科的研究中都获得了丰富的成果【7，8】。社交网络中的最近研究表明，桥接不同团体的用户具有很大的潜力从这些团体中获取可用资源和获得信息流的多个源。社会学中关于社交网络中的位置如何使占据它们的个体受益有一些已确立的想法【9】。一个想法是在不同团体中的个体间作为中介或桥接的位置具有更丰富的信息供应并对它们的网络关系具有更多的控制。这个概念构成了结构洞理论的基础【】，表明占据这种桥接位置的个体具有优势。例如，如果一个研究者跨越一个结构洞，他她可以将一个团体的思想和技术应用到另一个团体面临的问题上，或综合不同团体的想法进行创新。万方数据安徽大学201
34、7届硕士学位论文 基于社团结构的结构洞占据者发现方法研究一些维持不同社团间进行交流的桥接节点使社团的边界变得模糊，从另一个角度看，这些桥接节点被认为是神经学中的“枢纽”和社会学中的“结构洞占据者”，对其在社团间传输的信息具有更多的控*d E10一12。在神经学中，检查这些枢纽的功能和作用是特别令人感兴趣的，因为它们在建立和维持有效的大脑全局通信中起着中心作用，是健康脑功能的关键特征【lo，12】。在社会学中，结构洞理论【1】认为个体通过填充社团间的“洞”将获得更多潜在资源。结构洞占据者固有的连接多个社团，有效地将不同社团连接到弱结合的网络，现实世界网络中明确定义的社团在没有考虑结构洞占据者存在
35、的情况下很难找到。社会学的一些研究中己指出结构洞能够为跨越它的个体带来信息利益和控制利益，不同领域的学者将结构洞理论与学科知识相结合用以研究。如经济学、管理学和情报学等领域的研究者对结构洞理论产生了广泛的关注，并且在软件合作网络【8】、企业组织网络【13】、经济网络14】、群体内部组织网络【9，151和发明家网络161等网络中都有研究。从计算的角度来说，对结构洞的研究可以帮助分析网络中的信息流是如何在社团间传播的，跨越结构洞获得信息对网络信息传播的意义【17l，以及帮助分析网络中个体之间的凝聚性和结构等位属性等111，18，191。发现结构洞后可以帮助优化网络性能，如通过优化结构洞在网络规模和
36、多样性之间寻求平衡，从而提高网络的效率和性能【，20。目前，结构洞的研究包括结构洞占据者的度量研究和挖掘模型研究，以及结构洞占据者对网络性能的影响。如Lou和Tang的研列111中指出，大型社交网络Twitter中1的结构洞占据者，控制了25的信息传播。他们提出了两个挖掘topk个结构洞占据者的模型及其算法HIS和MaxD，并将其应用到科研合著网络、Twitter网络和发明家网络中，研究结构洞占据者在不同类型网络内信息传播过程中的作用。大多数社会网络表现出所谓的社团结构属性，即一个网络中的节点可以分为不同的连通群(社团)的集合【2】，在相同社团中的节点具有相似的属性。社团在网络的信息传播中发挥
37、重要的作用，信息在社团内传播很快并通过社团边界或桥节点扩散到其他社团。另一方面，社会学家之间一致认为【】，一个人在不同社团间起桥接作用时，可以从这些社团获得更多的潜在资源，并对正在传播的信息有更多的控制。伯特【l】研究了许多组织的社会结构，并且结构洞的概念蕴含着桥接不同群体并可以获得利益的位置，它表明单个社团内的信息趋向于同质的，非冗万方数据第一章绪论余信息通常是通过不同社团间的联系获得的【2l】。因此，如果一个人和来自多个团体的人建立联系，则将获得更多的利益。结构洞占据者有着广泛的应用。在社团检测中，确定连接不同群体的中心枢纽，可以帮助隔离和识别社团122l。在传染病和谣言传播中，隔离结构洞
38、占据者可以阻止感染和谣言传播到其他社团【23，24l。在病毒营销中，最具影响力的结构洞占据者可以加速新产品营销到不同群体25,26】。因此，结合社团结构发现结构洞占据者对现实网络具有更重要的价值和意义。12国内外研究现状几乎所有的复杂系统，如社会、信息、技术、传输等系统都可以表示为网络。节点表示这些系统中的各种元素，元素之间的关系称为边。研究者利用不同理论和方法可以获得对这些复杂系统的特征更深层的理解，从而对系统的功能进行更好的预测和控Nt2，】。重要节点的识别是网络结构研究中的一个重要问题，已有研究将重要节点定义为相对其他节点可以很大程度影响网络结构和功能的一些特殊节点，这些重要节点的研究包
39、括意见领袖【28】，结构洞占据者掣1l。近年来，越来越多的研究者集中于研究社交网络中的结构洞位置怎样使占据它们的人受益1991。根据伯特的理论【l，13，19，29，桥接没有连接关系的个体占据了结构洞位置，这将导致有利的结果。个体将通过填充这样的“洞”从人或团体之间受益，伯特认为跨越结构洞的个体将通过信息过滤获得更多的竞争优势和创新能力，这些“结构洞”是参与者间的网络间隙并会产生企业机遇。结构洞理论被广泛应用到社会学领域的研究中，并获得了一定的研究成果。胡蓉和邓小昭【s01结合结构洞理论对个人人际情报网络进行分析，提出一个企业行动者个人人际情报网络辅助分析系统来识别出情报网络中的结构洞。盛亚和
40、范栋梁【31】考虑到结构洞占据者通过控制资源流动来使自己获益，并结合结构洞占据者的桥接作用提出了结构洞分类理论，探讨了结构洞分类理论在创新网络中的应用价值。研究者通过分析结构洞的属性和特征，提出一些基于网络全局信息或局部信息的结构洞度量指标。伯特提出4个定量描述结构洞的度量指标【1，13,19，即约束度、有效规模、效率和等级度：Freeman提出介数中心性指标32】；Newman等人【33】提出局部聚类系数；邓世果等人【34】提出一种基于基尼系数的指标衡量结构洞，万方数据安徽大学2017届硕士学位论文 基于社团结构的结构洞占据者发现方法研究并讨论贡献度和结构洞程度之间的关系；Rezvani等人
41、f35】分析伯特提出的结构洞定义，并基于个体的邻居节点数和连接的社团数提出一种利用节点社团信息的结构洞度量指标。在对结构洞理论进行深入研究的过程中，研究者基于网络拓扑提出不同的结构洞模型【11，20，35-37。Goyal和VegaRedondo36将结构洞占据者表示为位于不同节点对之间大量最短路径上的节点，提出网络形成模型来模拟社会网络中结构洞的形成过程，并认为当节点么位于任意长的BC路径上，且作为节点B和C的中介时，都将获得潜在利益。由于统计所有的最短路径是耗时操作，Tang等人13 7】提出2-Step方法即只统计长度为2的最短路径。Kleinberg等人【20】从战略和动态方面研究了结
42、构洞理论，进一步扩充了伯特等研究者的工作。他们模拟了这样的过程，即当所有个体都在竞争桥接位置的时候，社会网络随着时间是如何改变的。Buskens和Van【9】使用博弈论方法来模拟具有结构洞的网络形成过程，认为节点么只有处在节点B和C中问时才能获益。Bruggeman等人38】考虑了生态位重叠导致的分散竞争对网络中个体的结构自主性的影响，修正了伯特的模型。随着对结构洞的价值和意义继续深入研究，研究者提出多种结构洞发现算法，在不同结构和类型的复杂网络中准确发现结构洞占据者。Zhang等人【18】认为网络中很难存在单节点形成的结构洞，他们在结构洞理论的基础上提出“广义结构洞”概念。他们认为广义结构洞
43、在社交网络的许多方面都起到重要的作用，如社团之间的交流，创新扩散和信息传播等，并根据谱图理论提出了一种新的启发式“广义结构洞”发现方法DGSH。结构洞是模糊社交网络分析中的关键问题，目前已经有许多模糊结构洞的评价标准，如关键模糊结构洞、一般模糊结构洞、强模糊结构洞和弱模糊结构洞掣3，】。由于有向模糊社交网络中的边具有有向模糊关系且包含丰富的信息，对有向模糊社交网络设计结构洞标准的需求不断增长，Hu和Zhang391将结构洞理论扩展到有向模糊社交网络，揭露了有向模糊社交网络的更多结构化信息，并提出单向模糊结构洞和双向模糊结构洞的挖掘算法，分别计算行动者占据的单向和双向模糊结构洞个数。Liao等人
44、【40】将结构洞理论引入到无向模糊社交网络中，研究了计算行动者占据结构洞个数的方法和结构洞的分类方法，且探讨了其在模糊技术创新网络中的应用。Lou和Tangill在假设网络社团结构己知的情况下，基于两级信息流理论和最小割分别提出两个结构洞占4万方数据第一章绪论据者的挖掘模型HIS和MaxD。结构洞是网络中存在的一种“缺口”，也代表着不同团体间交流的桥梁，结构洞在网络中的信息传播过程中与社团桥节点的作用相似；一些研究者考虑到结构洞的“缺口”特征和社团桥节点在识别传染源41,42】中的作用，并应用到相应问题领域。徐久强等人【43】通过对复杂网络中结构洞和紧密度这两个特征量进行计算统计，与软件网络中
45、的度进行关系拟合，并引入到软件网络作为参考特征量，可以量化软件网络中的节点依赖程度和中心化程度。Li等人【441将结构洞理论引入到软件网络中，从多粒度角度研究软件网络的拓扑特征，可以帮助研究者更深入的理解不同规模软件的结构特征。Jiang等人【。1】预期社团桥即连接社团间边的节点在信息从一个社团传播到其他社团的过程中起到关键作用。并且，这些社团桥可以反映传播的方向和速度，这样在传感器监视下可以合理的分配传感器识别传染源。Louni等人【42】选择位于社团间并且介数高的节点作为传感器，使相对原始高斯方法可以减少3数量的传感器。韩忠明等人【。s】考虑结构洞节点在信息传播中起到重要作用，并认为关键节
46、点排序问题不能忽略除处于结构洞位置的节点。根据相关结构洞衡量指标，提出一种可以结合结构洞特征和网络节点其他重要性特征的一种面向结构洞的关键节点排序方法。大部分网络呈现出社团结构，即网络中的节点可以划分为不同的群组【2】。社团结构对网络中的信息传播有很大影响，信息在社团内传播快而社团间较慢，占据不同社团间桥接位置的节点可以获得不同社团中的异质性信息和资源。伯特指出结构洞就是桥接不同群组并使自己获益的位置1】，即结构洞定义中暗含着网络可以划分为不同的团体。结合社团结构可以更好的发现网络中的结构洞占据者，可以加深理解结构洞占据者在团体间信息传播过程中发挥的作用。因此，本文提出基于社团结构解决结构洞占据者的发现问题。13本文主要内容及章节安排结构洞占据者发现的研究对网络结构理论及稳定性研究有着重要意义，研究者己提出不同的结构洞占据者发现方法。因此本文从多粒度社团结构和网络拓扑结合社团内部结构两个方面分析结构洞占据者的特征，通过对节点在多粒度网络中跨越结构