基于社区发现的社交网络结构洞并行迭代挖掘算法

《基于社区发现的社交网络结构洞并行迭代挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC学位论文基于社区发现的社交网络结构洞并行迭代挖掘算法作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：刘志诚鲍玉斌教授东北大学信息科学与工程学院硕士学科类别：工学计算机软件与理论2014年6月论文答辩日期：2014年6月2014年7月答辩委员会主席：于戈赵志滨王溪波东北大学2014年6月万方数据AThesisinComputerSoftwareandTheoryParallelIterativeAlgorithmofStructuralHolesMiningbasedonCommuni

2、tyDetectiononSocialNetworksbyLiuZhichengSupervisor：ProfessorBaoYubinNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢二E，罨象。学位论文作者签名：训之蚁Et期：2．0J哗6闫n日学位论文版权使用

3、授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年i学位论文作者签名：叫未蛟签字日期：2·J博6珥2z日新签名：杰珊签字日期：z口节午勿哥可】了万方数据东北大学硕士学位论文摘要基于社区发现的社交网络结构洞并行迭代挖掘算法古蠡iE手陶要随着Facebook，Twitter等网站的兴起，社交网

4、络的规模日趋复杂和庞大。通常，网络呈现社区分布结构，而社区间非冗余关系的存在形成了网络的漏洞。分析这些社区和漏洞可以了解网络中的群落分布和竞争优势，是社会关系网络分析中重要的基础性研究，并己成为当今学术界和工业界的热点话题。目前，经典的社区发现算法包括Newman等人提出的GN算法及其改进、基于评价社区结构的Q函数算法和基于clique发现的算法等。然而，这些算法时间复杂度较高，不适用于大型社交网络的处理。本文借鉴COPRA算法的标签传播机制，简化社区发现的过程，提出一种基于BSP模型的并行迭代算法PCOPRA，并最终应用于BC．BSP系

5、统中。与此同时，针对COPRA算法的缺点，本文进行了两点改进：(1)为避免因COPRA算法的同步标签传播而导致的标签振荡现象，使得算法无法收敛；也为避免因异步标签传播而导致挖掘结果的不稳定，本文提出了标签传播的半异步迭代机制。通过同／异步交替运行的方式，算法可结合两种迭代各自的优点，在确保结果稳定性的同时加快算法收敛速度，获得更好的性能。(2)为避免COPRA算法因对网络未知全局参数的过度依赖而影响社区挖掘结果的准确性，本文通过各节点对周围邻居社区情况的判别来自主决定网络参数，增加了社区发现过程的灵活性，提高了挖掘效率。除此之外，为支持标

6、签的异步迭代更新，本文对BC．BSP系统的同步模型做了扩展。通过在当前超步提前获取下一超步的消息来实现顶点的跨步更新，用以支持对增量迭代、标签传播等应用的快速处理。社交网络上的结构洞挖掘仍缺乏一个完备的理论算法，特别是对大型网络的挖掘。针对以上问题，本文贡献如下：(1)基于社区发现的结果，并借鉴Tang等人提出的HIS结构洞模型，设计并实现了一种改进后的基于BSP模型的并行结构洞挖掘算法PHIS，并最终应用于BC．BSP系统之上。(2)通过对节点更新规则的分析，从减少节点计算量和消息通信量的角度对算法进行了优化，很大程度地提升了性能。本文

7、所提出的并行化算法基于BSP模型。实验表明，在大规模社交网络中，算法可以在有效的时间内挖掘出高质量的社区和结构洞。关键词：社交网络；标签传播；重叠社区；结构洞；并行迭代；BSP万方数据东北大学硕士学位论文AbstractParallelIterativeAlgorithmofStructuralHolesMiningbasedonCommunityDetectiononSocialNetworksAbstractWlththeriseofFacebook，Twitterandetc，thescaleofsocialnetworkshasb

8、ecomelargerandmorecomplexincreasingly．Typically,thenetworkspresentthedistributionofcommunitiesan