基于标签传播的社区发现算法研究及其并行化
发布时间：2021-09-02 16:31
随着社交网络的不断发展,社区发现已经成为复杂网络领域的一个重要的研究热点。若干个社区组成了一个完整的网络,在社区的内部,节点之间的连接相对紧密,而社区与社区之间节点间的连接则相对松散。标签传播算法LPA（Label Propagation Algorithm）是社区发现算法中比较优秀的算法。它的线性的时间复杂度是它的一大优势。虽然LPA有很多的优点,但是缺点也是非常明显的。由于标签的随机选择,LPA不能保证每次结果的一致性;此外,在多次迭代之后,可能会出现大的社区将小社区吞并的现象。结合以上内容,本文在LPA的基础上改进扩展出了两个算法,具体的研究成果如下所示:（1）LPA的优化改进LPA算法不包含任何参数,主要对标签传播及更新进行优化。在基于概率和相似度的标签传播算法 PSLPA（Probability and Similarity based Label Propagation Algorithm）中,结合节点间的概率以及相似度,并在标签传播的过程中使用了自适应标签选择的方式对节点标签进行更新。在基于节点权重和随机游走的标签传播算法WRWILPA（Weightand Random ...
【文章来源】：南京信息工程大学江苏省
【文章页数】：58 页
【学位级别】：硕士
【部分图文】：
图２－１标签震荡７Ｋ意图??除此之外，签播法可能出现“”区，当一区签己经
（ｃ）?２－ｓｈｅｌｌ中的节点?（ｄ）?３－ｓｈｅｌ丨中的节点??图３－１?—个可分解为３个ｓｈｅｌｌ的网络示意图??对于图３－１?（ａ）中的网络图，各个节点所属的ｓｈｅｌｌ以及其ｉｔｅｒａｔｉｏｎ值如表３－１所?表分解后节点所属ｓｈｅｌｌ及ｉｔｅｍｔｉｙｎ值?节点?ｉｔｅｒａｔｉｏｎ?值???一?１－ｓｈｅｌｌ?￣９，１０，１１，１２，１３，１５，１７，１８，１９，２０＂?１?一?１－ｓｈｅｌｌ?１４，１６?２??一?２－ｓｈｅｌｌ?５，６，７，８?—?１?￣?３－ｓｈｅｌｌ?１，２，３，４?１?．２基于概率和相似度的标签传播方法??在传统的标签传播算法中，邻居节点之间并没有什么差异性，都是被同等对待。实际情况不是这样，不同的邻居节点可能对该节点有不同的影响力，所以为每一赋予一个权重是很合理的选择。ＰＳＬＰＡ根据以下的步骤来进行节点标签的选择以
火ｑ）和火《７．）分别表示节点ｑ和％的度，ｉＮＴｈ）表示节点ｎ，．的所有邻居节点集??合，使用／ＣＡ＾）表示节点ｑ的邻居索引，从式子中可以看出／ａｖ（？ｆ）ｅ［ｏ，ｉ］。??将图３．２作为例子，从图中可以看出节点１，９，?１４，?１７是度为１的叶子节点，节点１??只有一个邻居节点，为节点６，所以火遍历图中的１７个节点，可??以得到节点１０及其所有邻居的度之和为最大的２３，所以＾〇＼＾）＝５／２３?＝?０．２２，即节点??１的邻居索引值为０．２２；依次计算其余叶子节点，可以得到ＪＣＡＴ（％）－４／２３?＝?０．１７，??７〇＼＾４）＝７／２３?＝?０．３０，?７〇＼＾７）＝２／２３?＝?０．０９。从结果中可以清楚的看到，邻居索引／ＣＡＴ??值可以有效的区分拥有相同度的节点。??定义２．给定一个社交网络Ｇ（Ｖ，Ｅ），通过Ｋ－Ｓｈｅｌｌ分解方法，每个节点都被赋予一个??馬值。对于每一轮Ｋ－Ｓｈｅｌｌ分解，假设迭代次数为／？，并且节点ｑ是在第ｎ次迭代中删??除的，这里因此位置索引可以计算为表３－１列出了整个Ｋ－Ｓｈｅｌｌ分解??的过程。结合公式（１）
【参考文献】：
期刊论文
[1]基于夹角余弦的证据组合方法[J]. 胡嘉骥,李新德,王丰羽. 模式识别与人工智能. 2015(09)
[2]Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks[J]. 武志昊,林友芳,Steve Gregory,万怀宇School of Computer and Information Technology,Beijing Jiaotong University,田盛丰. Journal of Computer Science & Technology. 2012(03)
硕士论文
[1]基于SCAN算法的社区发现算法研究[D]. 王耀.南京信息工程大学 2016
本文编号：3379346
【文章来源】：南京信息工程大学江苏省
【文章页数】：58 页
【学位级别】：硕士
【部分图文】：
图２－１标签震荡７Ｋ意图??除此之外，签播法可能出现“”区，当一区签己经
（ｃ）?２－ｓｈｅｌｌ中的节点?（ｄ）?３－ｓｈｅｌ丨中的节点??图３－１?—个可分解为３个ｓｈｅｌｌ的网络示意图??对于图３－１?（ａ）中的网络图，各个节点所属的ｓｈｅｌｌ以及其ｉｔｅｒａｔｉｏｎ值如表３－１所?表分解后节点所属ｓｈｅｌｌ及ｉｔｅｍｔｉｙｎ值?节点?ｉｔｅｒａｔｉｏｎ?值???一?１－ｓｈｅｌｌ?￣９，１０，１１，１２，１３，１５，１７，１８，１９，２０＂?１?一?１－ｓｈｅｌｌ?１４，１６?２??一?２－ｓｈｅｌｌ?５，６，７，８?—?１?￣?３－ｓｈｅｌｌ?１，２，３，４?１?．２基于概率和相似度的标签传播方法??在传统的标签传播算法中，邻居节点之间并没有什么差异性，都是被同等对待。实际情况不是这样，不同的邻居节点可能对该节点有不同的影响力，所以为每一赋予一个权重是很合理的选择。ＰＳＬＰＡ根据以下的步骤来进行节点标签的选择以
火ｑ）和火《７．）分别表示节点ｑ和％的度，ｉＮＴｈ）表示节点ｎ，．的所有邻居节点集??合，使用／ＣＡ＾）表示节点ｑ的邻居索引，从式子中可以看出／ａｖ（？ｆ）ｅ［ｏ，ｉ］。??将图３．２作为例子，从图中可以看出节点１，９，?１４，?１７是度为１的叶子节点，节点１??只有一个邻居节点，为节点６，所以火遍历图中的１７个节点，可??以得到节点１０及其所有邻居的度之和为最大的２３，所以＾〇＼＾）＝５／２３?＝?０．２２，即节点??１的邻居索引值为０．２２；依次计算其余叶子节点，可以得到ＪＣＡＴ（％）－４／２３?＝?０．１７，??７〇＼＾４）＝７／２３?＝?０．３０，?７〇＼＾７）＝２／２３?＝?０．０９。从结果中可以清楚的看到，邻居索引／ＣＡＴ??值可以有效的区分拥有相同度的节点。??定义２．给定一个社交网络Ｇ（Ｖ，Ｅ），通过Ｋ－Ｓｈｅｌｌ分解方法，每个节点都被赋予一个??馬值。对于每一轮Ｋ－Ｓｈｅｌｌ分解，假设迭代次数为／？，并且节点ｑ是在第ｎ次迭代中删??除的，这里因此位置索引可以计算为表３－１列出了整个Ｋ－Ｓｈｅｌｌ分解??的过程。结合公式（１）
【参考文献】：
期刊论文
[1]基于夹角余弦的证据组合方法[J]. 胡嘉骥,李新德,王丰羽. 模式识别与人工智能. 2015(09)
[2]Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks[J]. 武志昊,林友芳,Steve Gregory,万怀宇School of Computer and Information Technology,Beijing Jiaotong University,田盛丰. Journal of Computer Science & Technology. 2012(03)
硕士论文
[1]基于SCAN算法的社区发现算法研究[D]. 王耀.南京信息工程大学 2016
本文编号：3379346
本文链接：https://www.wllwen.com/kejilunwen/yysx/3379346.html
