一种新的重叠社区发现算法*

基于节点的中心度和节点对社区的适应度,提出了一种新的重叠社区发现算法。该算法以中心度很大的节点作为初始社区,然后访问社区的邻居节点,把对社区适应度最大的节点加入到社区。如果节点对多个社区都具有很大的适应度,则这些节点归属于多个社区。考虑到社区之间的重叠性,将社区相似度很大的社区合并为一个社区。将该算法应用到Zachary空手道俱乐部网络和海豚社会网络中,实验表明该算法能够很好地划分出网络中的重叠社区。     

基于节点拓扑结构和属性的重叠社区检测算法

近些年来,网络中的重叠社区检测应用越来越广泛,这极大引起了人们的兴趣。通常重叠社区检测只考虑节点的拓扑结构信息,忽略了节点的属性信息,这可能会遗漏数据间的重要结构。本文提出了一种基于节点拓扑结构和属性相似度的局部社区检测算法。首先,计算出节点与社区之间属性相似度。其次,为挖掘内部紧耦合的社区,计算出能够表示耦合性的模块度增量。最后,通过融合多个已检测到局部社区,计算出隶属矩阵从而获取全局重叠社区结构。在三个有真实社区的数据集上的实验结果从内部指标模块度和与真实社区的比较验证了基于节点拓扑结构和属性相似度的重叠社区检测算法比目前基于节点结构的社区检测算法在效率和有效性上有所提升。     

机会网络中基于社区的高效消息传输算法

针对机会社会网络中现有基于社区的消息传输算法(OSNCMTS)在社区内存在节点积压消息分发任务、在社区间存在盲目选择活跃节点转发信息的问题,提出一种基于社区的高效机会网络路由算法(HECMTS)。在HECMTS算法中,首先,采用极值优先(EO)算法划分社区并将划分的社区矩阵分发给社区节点;其次,采用社区矩阵和消息到目的节点成功率相结合的方法分配社区内消息副本数;最后,利用活跃节点往返不同社区的机会收集活跃节点信息,然后查询这些活跃节点信息从中选取合适的活跃节点完成社区间消息传输。仿真结果表明,与OSNCMTS算法相比,HECMTS算法在路由开销性能和平均端到端时延性能上分别至少下降了19%和16%。     

基于种子节点选择的重叠社区发现算法*

识别网络社区对于了解社会网络的结构和功能具有重要意义。由于网络中某些节点可能属于多个社区,因此重叠社区的研究已经吸引了人们越来越多的关注。本文针对目前从局部社区扩展成全局社区时有关算法的种子节点选择不合理的情形,提出了一种基于种子节点选择的重叠社区发现算法。本算法首先根据影响力函数找出局部影响力最大的节点,由这些节点构成的种子集合较好的分布在整个网络中,然后以这些种子点构造初始社区,根据设定的吸引度函数选择性添加节点来进行社区扩展。实验结果表明,该算法在真实网络上进行测试时能够有效的挖掘网络中的重叠社区。     

基于局部语义聚类的语义重叠社区发现算法

语义社会网络是一种包含信息节点及社会关系构成的新型复杂网络,因此以节点邻接关系为挖掘对象的传统社会网络社区发现算法无法有效处理语义社会网络重叠社区发现问题。针对这一问题,提出基于局部语义聚类的语义社会网络重叠社区发现算法,该算法：1）以 LDA （latent Dirichlet allocation）模型为语义信息模型,利用 Gibbs 取样法建立节点语义信息到语义空间的量化映射;2）以节点间语义坐标的相对熵作为节点语义相似度的度量,建立节点相似度矩阵;3）根据社会网络的局部小世界特性,提出语义社会网络的局部社区结构 S‐fitness 模型,并根据 S‐fitness 模型建立了局部语义聚类算法（local semantic clusterm ,LSC）;4）提出可度量语义社区发现结果的语义模块度模型,并通过实验分析,验证了算法及语义模块度模型的有效性及可行性。     

一种面向度中心性及重叠网络社区的发现算法

针对社会网络中存在较多以度中心节点为中心并且具有多社区重叠节点的网络社区结构,提出了一种面向度中心性及重叠网络社区的两阶段发现算法。第一阶段发现初始社区:选取度最大的Top-k个节点作为候选中心节点,并将每个节点与其邻居节点形成候选初始社区,其中如果某候选社区与已形成的初始社区的重叠度低于阈值,则形成一个新的初始社区;第二阶段调整社区划分:通过偏离度机制进行调整,将偏离度最大值对应的节点划分到连接紧密的相应社区内,形成最终社区划分。实验表明,该方法不仅能够揭示网络中以某个节点为中心的密集的社区结构,还能有效处理初始社区不同程度的重叠问题。相比现有算法,所提方法对预先输入的候选初始社区数k值不敏感,并具有较高的准确性和灵活性。     

基于重叠社区和结构洞度的社会网络结构洞识别算法

结构洞是社会网络中的关键位置,对信息扩散起中介作用。为高效、准确地辨识具有社团结构的社会网络中占据结构洞的节点,提出了一种基于重叠社区和结构洞度的结构洞识别算法,旨在找到一组最具信息优势和控制优势的节点。基本思想是首先定位社区之间的重叠节点,然后利用节点的邻接差异和连接的社区差异衡量其非冗余性,计算出重叠节点的结构洞度,通过对结构洞度值升序排列发现占据结构洞的节点集。应用于实际数据集的实验结果表明,与网络约束系数算法、中介中心度算法、MaxD算法相比,该算法的识别准确度最高,时间复杂度最低。     

复杂网络局部社区挖掘的节点接近度算法

为了准确、快速地发现大规模复杂网络中的局部社区,提出了一种基于节点接近度的局部社区发现算法。该算法以最大度节点作为起始节点,利用节点接近度和局部社区Q值不断搜索其邻居节点,将接近度最大的节点加入初始社区形成新的初始社区;同时,该算法也可以应用于复杂网络全局社区结构的划分。对2个典型复杂网络进行了局部社区挖掘分析,实验结果表明,该算法能够有效识别隐藏在实验网络中的局部社区。针对稀疏网络,该算法的时间复杂度为O（nlog（n））,n为网络节点数。     

基于话题综合因子分析的语义社会网络社区发现算法

针对一般社会网络社区发现算法仅考虑各节点的邻接关系,所划分的社区仅为一元关系社区,不能代表社区成员的语义相似性且无法处理具有多元语义话题的语义社会网络社区发现问题,提出基于话题因子分析的语义社会网络社区发现算法.该算法将节点的多元信息抽象为话题,先以多元话题综合因子作为节点话题信息度量,以节点间的话题密度差异作为节点聚合方向,构建初始社区结构;再以最大化社区内部话题信息相似度和最小化社区外部话题信息相似度为目标建立语义社区发现的目标函数及节点变动的代价函数;再以初始社区结构和代价函数作为初始解和判断准则,以节点变动的代价函数值为参数,建立全局优化的模拟退火策略优化语义社区结构,实现语义社会网络的语义社区发现;最后通过实验分析验证了算法的有效性.     

基于共同好友数的在线社会网络社区发现算法

为了快速准确地找到在线社会网络的社区结构,提出了一种基于共同好友数和节点邻居信息的社区结构发现算法。该算法以共同好友数最多的两个节点为初始社区,不断寻找与社区连接性最强的节点,并以节点Q值为衡量标准,判断是否将该节点加入到初始社区中,最后根据节点邻居所在初始社区信息确定最终的社区划分。针对两个经典社会网络和人工生成网络数据的实验划分结果表明,该算法是可行和有效的。     

基于子网络结构属性的网络分割研究

Girvan和Newman等人提出了一种基于“中间状态边”概念的网络分割算法,成为研究网络结构的代表性算法。根据“中间状态边”概念,提出了一种新颖的网络分割算法：该算法通过分析构成子网络的两个结构属性,给出了一种划分子网络的方法。根据计算机生成的随机网络和一些真实世界网络的子网络划分实验表明,该算法具有划分准确、计算量小的优点。     

基于局部思想的在线社区划分算法

为了快速准确地对在线社会网络进行社区划分,提出了一种基于局部思想的社区划分算法。该算法利用节点和社区聚集系数的性质,结合局部模块度将节点划分成相对独立的社区。算法运行时,只需要了解与目标节点相关的局部网络信息,时间复杂度相对较低,并且也可以用来对整个在线社会网络进行社区划分。利用该算法分别对Zachary空手道俱乐部网络和在线社会网络进行划分实验,得到满意的结果。     

基于权重信息挖掘社会网络中的隐含社团

社团结构是一种普遍存在于各类真实网络中的结构特性.挖掘网络的社团结构对于理解网络的功能与行为有着重要作用.然而,现有的各种社团挖掘算法仅仅基于网络拓扑结构信息,而忽视了蕴涵于真实社会网络边权信息中丰富的语义信息.目前普遍使用的基于模块性最大化的社团挖掘算法倾向于将小社团合并,这使得语义上丰富的小社团容易湮灭于基于拓扑结构信息所挖掘出的大社团中.而挖掘出这些隐含于大社团中的有着丰富语义内涵的小社团对于加深社会网络语义层面的理解有着重要作用.为此,提出一个接近线性复杂度的有权网络社团挖掘算法.通过充分利用权重信息,算法可以将社会网络划分为富含语义信息的粒度较细且相对较小的隐含社团.通过对基于DBLP作者合作网络的实证分析,证实了新算法的有效性和高效性.     

基于信息瓶颈的社区发现

该文提出一种映射方法,把单部网络变换成二部图网络.针对得到的二部图网络,在信息论的框架下,提出了一种基于信息瓶颈的社区发现方法.该方法通过寻找网络的最优压缩表示来发现网络的社区结构,最优压缩表示尽可能多地保留原始网络的拓扑特征.在真实数据集和计算机产生的数据集上的实验表明,该方法能够有效地发现网络的社区结构.另外,对于有向网络的社区发现,现有方法忽略有向网络中边的方向而作为无向网络来处理,损失了有向的网络的方向信息,文中提出的社区发现方法能够很好地解决这一问题,并能从有向网络中挖掘出一些现有方法无法发现的知识,这一特点使得该文的方法比现有方法更适用于解决像WWW这样的有向网络.同时,真实世界的许多网络本身就是二部图网络,相对于现有的社区发现方法,文中的方法可以直接应用于这类网络.     

基于群体智能的自组织重叠社团结构分析算法

社团结构分析是复杂网络研究的一项重要内容。基于群体智能思想提出了一种自组织的重叠社团结构分析算法SO^2CSA^2。基本思想是：把网络视为一个群体,网络节点是其中的一个个具有简单智能的个体,每个个体依据定义的社团连接分数自主决定要加入的社团（可同时加入多个社团）。首先在网络中寻找一组K-派系作为初始社团结构;在此基础上,所有个体迭代地选择其社团归属,最终整个网络的社团结构将逐渐生长出来;最后对获得的社团结构进行后处理,即调整少量节点的社团归属,以提高其质量。在一组合成网络和现实世界网络上的实验表明,SO^2CSA^2发现的社团结构的质量比两种对比算法（SLPA和OSLOM）更好,尤其是在网络中重叠节点较多或节点重叠度较大的情况下,社团结构质量的提升更为明显。     

基于信息熵的复杂网络社团划分建模和验证

社团结构是复杂网络最普遍和最重要的拓扑属性之一,社团结构的划分方法对分析复杂网络相关统计特性具有十分重要的理论意义.为了提高社团划分精度,提出了一种新的基于信息熵(information entropy)模块度的社团划分算法(简称IE算法).在有着确定社团结构的数据集和不确定社团结构的数据集上,通过选取Q值、社团划分个数、社团最大连通分量大小和强弱社团个数比例4个重要参数,将IE算法与两种最主要的基于模块度的划分算法GN(Girvan-Newman)和FastGN(Fast Girvan-Newman)进行对比,实验结果证明了IE算法在社团划分性能上优于GN和FastGN;将IE和其他7种最主要的经典社团算法进行时间复杂度分析,并在随机网络和真实网络上进行实验,结果表明该算法时间复杂度在GN与FastGN之间,时间复杂度小于GN而精确度优于GN,证明了在大多数数据集上IE算法的社团划分准确度优于传统基于点边比率的社团划分算法的准确度.     

基于社团划分的网络聚类布局算法

复杂网络日益受到广大专家和学者们的关注,对其进行可视化展示可以帮助用户发现复杂网络表征的复杂系统中隐藏的知识信息,对计算机科学、社会学、生物学等领域具有重要的意义。力导引布局算法是复杂网络可视化领域的主流算法,它用节点连接图的形式对复杂网络进行抽象表示,布局遵循一定的美学标准如节点的均匀分布、边长尽量一致等,这在一定程度上阻碍了对复杂网络的社团结构的展示。针对以上问题,本文提出引入基于度中心性的社团斥力与引力对力导引算法进行改进,以对复杂网络进行聚类布局。实验结果表明,本文算法可有效地展示复杂网络的社团结构,同时又能保留社团之间边缘节点的信息。     

一种基于增量式谱聚类的动态社区自适应发现算法

针对当前复杂网络动态社区发现的热点问题, 提出一种面向静态网络社区发现的链接相关线性谱聚类算法, 并在此基础上提出一种基于增量式谱聚类的动态社区自适应发现算法. 动态社区发现算法引入归一化图形拉普拉斯矩阵呈现复杂网络节点之间的关 系,采用拉普拉斯本征映射将节点投影到k维欧式空间.为解决离群节点影响谱聚类的效果和启发式确定复杂网络社区数量的问题, 利用提出的链接相关线性谱聚类算法发现初始时间片的社区结构, 使发现社区的过程能够以较低的时间开销自适应地挖掘复杂网络社区结构. 此后, 对于后续相邻的时间片, 提出的增量式谱聚类算法以前一时间片聚类获得的社区特征为基础, 通过调整链接相关线性谱聚类算法实现对后一时间片的增量聚类, 以达到自适应地发现复杂网络动态社区的目的. 在多个数据集的实验表明, 提出的链接相关线性谱聚类算法能够有效地检测出复杂网络中的社区结构以及基于 增量式谱聚类的动态社区自适应发现算法能够有效地挖掘网络中动态社区的演化过程.     

一种基于层次约简的多层网络社区发现算法

如何在多层网络中发现社区是一项巨大挑战。目前有些算法将多层网络表示成三阶张量,然后使用非负张量分解进行社区发现。但在多层网络的每层网络中存在很多社区之间的连接或每层网络都很稀疏的情况下,非负张量分解算法的准确率较差。为了解决这一问题,本文提出一种改进算法。先将原始多层网络进行层次约简,减少多层网络的层数,使其社区结构更加凸显,然后再使用非负张量分解算法进行社区发现。在人工数据集与真实数据集上的实验表明,本文所提出的框架在准确率上有明显的优势。