复杂网络的社团发现的发展历程.ppt

复杂网络的社团发现的发展历程,主要内容,1.选题背景2.研究现状3.主要研究的内容及要解决的问题4.工作计划,选题背景,社团是指在同一网络中，对于一个特定的集合内节点之间的连接比较紧密，但是集合与集合之间的连接比较稀疏，同一社团中的节点或有共同的性质或在网络中扮演着相同的角色。,选题背景,现实社会中有大量的社团结构，家庭，同事或者朋友等。在蛋白质蛋白质网络中，在同一社团内的蛋白质在细胞中都发挥着相同的特定指标；同样随着计算机技术的迅猛发展，虚拟网络也成为研究热点。,研究现状,单一关系网络的社团发现的算法,1.传统算法,2.分裂算法,3.基于模块度的算法,二分网络的社团发现,1.映射法,2.非映射法,多子网复合复杂网络的社团结构,基于子网复合的思路来求得社团结构。,4.动态算法,5.其他算法,传统算法,图分割：分成g个预定大小的群组，群组之间的边数数目最小。,聚类：把社区发现看做一组内容相似的物体集合，使用聚类算法。,研究现状,单一关系网络的社团发现的算法,1.传统算法,2.分裂算法,3.基于模块度的算法,二分网络的社团发现,1.映射法,2.非映射法,多子网复合复杂网络的社团结构,基于子网复合的思路来求得社团结构。,4.动态算法,5.其他算法,GN算法,其基本思想：（1）计算网络中具有最大介数的边。（2）从网络中移除介数最大的边。（3）重新计算网络中的最大介数的边，转移执行2)。如此迭代下去，最终获得社区的划分,研究现状,单一关系网络的社团发现的算法,1.传统算法,2.分裂算法,3.基于模块度的算法,二分网络的社团发现,1.映射法,2.非映射法,多子网复合复杂网络的社团结构,基于子网复合的思路来求得社团结构。,4.动态算法,5.其他算法,基于模块度的算法,一个网络的模块度就定义为该网络社团内部边数与相应的零模型的社团内部边数之差占整个网络边数M的比例。,研究现状,单一关系网络的社团发现的算法,1.传统算法,2.分裂算法,3.基于模块度的算法,二分网络的社团发现,1.映射法,2.非映射法,多子网复合复杂网络的社团结构,基于子网复合的思路来求得社团结构。,4.动态算法,5.其他算法,动态算法,自旋模型和同步算法在社区发现领域十分活跃，发了不少论文。随机游走是基于以下思想：如果存在很强的社区结构，那么随机游走器（randomwalker)会在社区内部停留更长的时间，因为社区内部的边密度比较高。,研究现状,单一关系网络的社团发现的算法,1.传统算法,2.分裂算法,3.基于模块度的算法,二分网络的社团发现,1.映射法,2.非映射法,多子网复合复杂网络的社团结构,基于子网复合的思路来求得社团结构。,4.动态算法,5.其他算法,其他算法,研究现状,单一关系网络的社团发现的算法,1.传统算法,2.分裂算法,3.基于模块度的算法,二分网络的社团发现,1.映射法,2.非映射法,多子网复合复杂网络的社团结构,基于子网复合的思路来求得社团结构。,4.动态算法,5.其他算法,二分网络的社团发现,随着二分网络的提出，针对于它的社团发现也成为了研究热点。二分网络指的是存在两类节点，连边只在不同节点之间存在的网络。,二分网络的社团发现,将二分网络先映射成单分网络，进而用较为成熟的单分网络的社团发现算法做进一步的划分。但是在映射过程中无法避免信息的缺失。,则而非映射法则是直接在二分网络网络上进行社团划分，例如，基于边集聚系数的社团发现算法等。,映射法,非映射法,研究现状,单一关系网络的社团发现的算法,1.传统算法,2.分裂算法,3.基于模块度的算法,二分网络的社团发现,1.映射法,2.非映射法,多子网复合复杂网络的社团结构,基于子网复合的思路来求得社团结构。,4.动态算法,5.其他算法,多子网复合复杂网络的社团结构的发现,多子网复合复杂网络是一种多种类型节点，多种连边关系的网络。,多子网复合复杂网的社团结构的发现,目前研究多子网复合复杂网络的思路大致是基于子网复合的思路来求得社团结构。,：整体的模块度,：子网y的模块度,：子网y的连边数与整体连边比例,存在的问题,易造成连接密度的高的子网中的社团被识别，而连接密度低的子网中的社团不被发现。,主要研究内容,1）基于多子网复合复杂网络的模型，研究当子网的连边密度不同时，采用子网信息复合的方法来进行社团划分，提出一种有效的思想或策略来有效地发现社团结构。2）基于多子网复合复杂网络的模型，研究当子网的网络类型不同时，子网与子网之间连边关系为一对一、一对多、多对多时，提出一种有效的思想或策略来有效地发现社团结构。3）以社交网络为例，建立能够描述社交网络的多子网复合复杂网络模型，在子网连边密度不同，子网的网络类型不一样，子网与子网的连边关系不同时，对提出的算法或思想进行实证研究。,解决的主要问题,1）基于多子网复合复杂网络的模型，研究当子网的连边密度不等，子网的网络类型不同，子网与子网的连边关系不同时，对应的有效发现社团结构