复杂网络中社团检测调研报告指导老师刘玉华教授学生.ppt

《复杂网络中社团检测调研报告指导老师刘玉华教授学生.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、复杂网络中社团检测调研报告指导老师：刘玉华教授学生：胡芳2014.1.121报告大纲一、复杂网络中社团的概念二、社团划分的相关工作三、社团划分的几种经典算法四、真实网络中几种典型的社团模型五、蚁群算法在社团应用中深入研究六、总结2一、复杂网络中社团的概念一个复杂的网络通常表示为一个无向图G（V，E），其中V是节点集（或顶点）和E是边集（或链接）。社团检测在复杂的网络本质上是一个聚类问题，这着重于检测密集连接的子图G1，G2……Gk，在G，其中G1,G2……Gk满足∪1≤i≤kGi=G和∩1≤I≤KGi=∅。直观地说，如果一个分区具有属性，在社团内部连接密集和社团之间连接稀疏，

2、这将被称为一个良好定义的聚类结果。3报告大纲一、复杂网络中社团的概念二、社团划分的相关工作三、社团划分的几种经典算法四、真实网络中几种典型的社团模型五、蚁群算法在社团应用中深入研究六、总结4二、社团划分的相关工作(1/5)在过去的十年中，社团发现的问题备受关注各种科学领域，包括物理学，社会学和计算机科学。许多采用不同的策略方法已经被提出和成功应用到一些具体的复杂网络。例如，Girvan和Newman提出GN算法，这是一种方法利用有关边介信息检测社团结构[1]。随后，Newman在Q函数的基础上提出了一种快速算法用于检测社团结构[2]。基于q-states的Potts模型，Re

3、ichardt和Bornholdt提出了一个社团的快速检测算法，该算法可以在没有预先知道社团数目的情况下检测重叠社团[3]。5二、社团划分的相关工作(2/5)通过基于网络模块化矩阵的特征向量的手段，Newman提出了谱算法的社团检测，在更短的运行时间获取比其他竞争方法更高质量的检测[4]。Radicchi等人给社团的两轮量化定义并提出了一种局部算法来检测社团，它可以有效地处理大规模网络[5]。Gergely等人用集团渗透的方法，以确定在复杂网络的密集连通子图[6]。Frey等人用亲和力传播来传递消息，并通过反复地划分数据点到来得出集群的典范[7]。Yang等人开发出一种新算法

4、（FEC），该算法基于代理的社团随机行走模型，从有标志的社会网络中识别社团[8]。6二、社团划分的相关工作(3/5)2012年，Faqeeh等提出了一种新的算法（称为FA），其中所采用的成块矩阵的特征向量来构造一个“投影空间”和使用某种在这个空间角距离来定义边界线，然后应用这个交界性和层次聚类方法来确定的复杂网络的社团结构[9]。Gong等人提出改进的Memetic算法（称为iMeme-Net），用来解决网络社团检测问题，结合标签传播（PGLP）战术，精英策略（ES），以及改进的模拟退火算法，并结合本地搜索（ISACLS）策略进行算法的设计[10]。7二、社团划分的相关工作(

5、4/5)Pizzuti提出了一种新的算法通过采用遗传算法（GA命名-NET）[11]发现在网络社区。该方法引入社团得分的概念来衡量一个网络社团一个分区的质量，并试图通过运行遗传算法来优化这个量。Liu等人提出了一种基于蚁群聚类模型，它采用的移动，拾取和下降式运营在电子邮件网络中进行节点群集[12]。为了降低聚类计算成本，又不降低结果的质量。Sadi等人使用蚁群优化（antcolonyoptimization，ACO）技术来在网络查找派系和分配这些派系为元结点，然后采用传统的算法来找到社团成员[13]。8二、社团划分的相关工作(5/5)为了进一步优化方法，作者随后使用了滚雪球抽

6、样的方法来生成子图，并行运行基于社团发现技术的ACO算法[14]。Zhang等人采取Q函数为目标函数，提出了一种动态社会网络中的社团挖掘方法，它使用了聚类中心的初始化，信息素更新和启发函数的指导战略，以实现集群解决方案[15]。在参考文献[16]中，Jin等人提出了一个名为ACOMRW的蚁群优化算法，其基本思想是逐步加强社团内的联系和逐渐减弱社团之间的联系。在每次迭代中，一个马尔可夫随机游走模型被蚂蚁（应该指蚂蚁优化算法）作为启发式规则，所有蚂蚁的局部解决方案，通过聚类集成，然后用于更新信息素矩阵聚合到一个全局的解决方案中。并逐渐收敛到一个解决方案，复杂网络的基本社会结构将变

7、得清晰可见。9报告大纲一、复杂网络中社团的概念二、社团划分的相关工作三、社团划分的几种经典算法四、真实网络中几种典型的社团模型五、蚁群算法在社团应用中深入研究六、总结10三、社团划分的几种经典算法(1/13)1、GN算法2、Kernighan-Lin算法3、基于Laplace图特征值的谱二分法4、FCM算法5、验证算法准确性参数与概念定义111、GN算法GN算法是一种分裂方法[17]。其基本思想是不断的从网络中移除介数(betweenness)最大的边。边介数定义为网络中经过每条边的最短路径的数目。具体