复杂网络基于局部模块度的社团划分方法

提出了一种基于局部模块度的社团划分算法,该算法的基本思想是将具有最大综合特征值的节点作为初始节点,然后从候选集中找到使局部模块度Q达到最大值时所对应的候选节点,将此节点合并到该社团中,更新候选集合直至Q值不再增加,此时该社团形成。由于算法仅需要利用节点的局部信息,因此时间复杂度很低,并且通过综合特征值,找到聚类中心,从而使得聚类效果大大提高。通过社会学中经典的Zachary网络表明了该算法的可行性,并得到满意的结果。

基于节点-模块置信度及局部模块度双重约束挖掘前列腺癌候选疾病模块

前列腺癌病因及发病机理研究有助于前列腺癌预防和治疗.目前,前列腺癌生化试验研究方法成本高、耗时,而基于网络计算方法容易受基因表达谱数据不完整、噪声高及实验样本数量少等约束.为此,本文提出一种基于节点-模块置信度及局部模块度的双重约束算法(命名为NMCOM),挖掘前列腺癌候选疾病模块.NMCOM算法不依赖基因表达谱数据,采用候选基因与致病表型之间一致性得分,候选基因与致病基因之间语义相似性得分融合排序策略,选取起始节点,并基于节点-模块置信度及局部模块度双重约束挖掘前列腺癌候选疾病模块.通过对挖掘出的模块进行富集分析,最终得到18个有显著意义的候选疾病基因模块.与单一打分排序方法及随机游走重开始方法相比,NMCOM融合排序策略的平均排名比小、AUC值大,且挖掘出结果明显优于其他模块挖掘算法,模块生物学意义显著.NMCOM算法不仅能准确有效地挖掘前列腺癌候选疾病模块,且可扩展挖掘其他疾病候选模块.

基于局部模块度的社区层次结构发现方法

为了发现复杂网络中社区之间的层次关系,提出了一种基于局部模块度的社区层次结构发现方法。文章方法克服了多分辨率方法无法给出整个网络的层次划分以及无法直接定位造成社区层次变化的分辨率等方面不足,选取网络中的大度数节点基于R公式进行社区层次结构探测,根据局部模块度值变化过程中产生的极大值和极小值定义了社区层次区分度来判断是否到达层次边界。并对网络进行裁剪,从不同的大度数节点出发来发现网络中的全部层次结构。在经典数据集和人工生成网络上进行了实验,并与现有算法进行比较,实验结果证明章算法的有效性。

模块度增量与局部模块度引导下的社区发现算法

社区结构是复杂网络的重要特性之一,基于层次聚类的社区发现算法很好地利用了模块度来挖掘网络中的社区结构,但其局限性也导致算法对社区结构复杂的网络划分不够准确、无法发现小于一定规模的社区。在层次聚类的基础上,提出引入局部模块度来弥补模块度在划分社区时的不足,避免可能出现的划分不合理情况。通过真实数据集和人工网络进行了验证,实验结果证明,该算法具有可行性与有效性。

一种基于局部模块度的增量式动态社区发现算法

为更好地适应大规模社会网络数据的应用要求,提出一种基于局部模块度的增量式动态社区发现算法。把对起始时间的社会网络执行静态社区发现获得的社区结构和局部模块度作为增量分析的基础,把局部模块度作为优化的条件,使用四种原子操作,逐步演化社区结构。使用社区结构的局部信息,提高了算法的运行效率。避免了设定参数的条件,提高了算法的适应性。实验结果表明,该算法具有一定的实际应用价值。

基于局部模块度社团划分算法的文本概念聚类新方法

提出一种将概念格和社团划分方法两种理论结合的文本聚类方法,首先将节点特征值权值按照从大到小的顺序映射到形式背景中,然后通过计算出形式背景中概念相似度的大小,构造L网络,最后根据局部模块度社团划分算法规则对待聚类文本进行聚类。

基于DeepWalk的局部社区发现算法

局部社区发现可以不依赖网络的整体结构计算出给定节点所在的社区,是社区发现研究中的一个重要问题,尤其在大网络数据分析中具有重要的应用意义.节点嵌入作为一种新的网络表示学习方法,给局部社区发现研究提供了新思路.为此,基于节点嵌入DeepWalk算法提出一种新的两阶段局部社区发现算法.第一阶段应用DeepWalk模型学习网络节点的向量表示,用低维向量表示网络节点;第二阶段通过选择最相似邻居的方法,从给定的起始节点逐渐向外扩展得到目标社区.在4个真实网络数据集上进行了实验,相比基准算法,所提算法取得了更高的准确率,实验结果验证了算法的有效性.

基于谱图小波的多尺度社区搜索方法

作为可捕获用户个性化信息的网络分析任务,社区搜索旨在挖掘满足内聚性要求的查询节点所在的社区。大多数现有社区搜索方法仅能定位查询节点所在的单尺度社区。据此,设计了一种基于谱图小波的多尺度社区搜索方法,利用谱图小波和局部模块度挖掘查询节点所在的多尺度社区。具体地,首先,构建模块度矩阵和拉普拉斯矩阵并进行矩阵分解得到相关特征向量;其次,结合谱图理论和图小波,设计了基于谱图小波的尺度依赖局部模块度;再次,以归一化拉普拉斯矩阵和局部模块度张成的特征空间为支撑,设计了线性规划问题,以求解在给定尺度下与查询相关的稀疏指示向量;最后,利用社区边界截断策略不断添加节点,使得局部模块度最大。人工网络和真实网络上的实验结果表明了方法的高效率和有效性。

异质信息网络中基于解耦图神经网络的社区搜索

在异质信息网络(HINs)中搜索包含给定查询节点的社区具有广泛的应用价值,如好友推荐、疫情监控等。现有HINs社区搜索方法大多基于预定义的子图模式对社区的拓扑结构施加一个严格的要求,忽略了节点间的属性相似性,导致结构关系弱而属性相似性高的社区难以定位,并且采用的全局搜索模式难以有效处理大规模的网络数据。为解决这些问题,首先设计解耦图神经网络和基于元路径的局部模块度,分别用于度量节点间的属性相似性和结构内聚性,并利用0/1背包问题优化属性和结构两种凝聚性度量指标,定义了最有价值的c大小社区搜索问题,进而提出了一种基于解耦图神经网络的价值最大化社区搜索模型,执行3个阶段的搜索过程。第一阶段,依据查询信息与元路径,构造候选子图,将搜索范围控制在查询节点的局部范围内,保证整个模型的搜索效率;第二阶段,利用解耦图神经网络,融合异质图信息和用户标签信息,计算节点间的属性相似度;第三阶段,根据社区定义以及凝聚性度量指标,设计贪心算法查找属性相似度高且结构凝聚的c大小社区。最后,在真实的同质和异质网络数据集上测试了搜索模型的性能,大量实验结果验证了模型的有效性和高效性。

基于主题与连接的局部社区划分算法

设计了一种基于主题与连接的局部社区划分算法。该算法结合节点的主题相似度和连接相似度,综合计算节点间的相似度。同时算法采用局部思想,避免了寻找初始的中心节点。此外,该算法引入了局部模块度作为社区划分的结束判断条件。该算法被应用到参与"海地地震"相关话题讨论的Twitter微博用户数据集上,并与单纯基于链接、单纯基于主题以及基于主题和链接的社区划分算法在同样数据集的划分结果进行对比,结果表明:从纯度和熵的评估角度看,本文算法更具优越性。

基于稠密子团和边聚类系数的局部社团挖掘算法

发掘复杂网络的社团结构,有助于深入理解网络结构属性及其功能重要性。本文通过定义稠密子团,结合边聚类系数和局部模块度,提出一种DIDE社团挖掘算法。该算法通过选取稠密子团作为初始聚类团,利用边聚类系数扩张该稠密子团,最大化局部模块度值来生成社团结构。在计算机生成网络、三社团网络、Zachary网络和美国足球俱乐部网络上进行社团划分,验证该算法的可行性和有效性。

面向二分网络的谱近似社区搜索方法

社区搜索旨在从网络中查找给定查询节点所在的局部社区,基于谱的社区搜索方法是流行的方法之一。现有基于谱的社区搜索方法多面向简单网络而无法处理具有2类实体关联的二分网络,且面向二分网络的社区挖掘方法多是对网络进行整体划分。据此,提出了面向二分网络的谱近似社区搜索方法,旨在将谱方法引入到二分网络中进而精确定位与查询节点关联紧密的社区。具体来说,首先考虑二分网络中2类实体的关联,基于局部模块度设计了面向二分网络的局部模块度;其次,基于谱图理论,在二分网络上利用融合不同实体关联的模块度矩阵局部逼近特征子空间,设计了适用于二分网络的谱方法;最后,利用结合谱性质的二分网络上的局部模块度,设计了谱子空间中以查询节点集为支撑的稀疏指示向量的线性规划问题,目标社区可通过线性规划问题的求解而获得。真实数据集上的实验结果表明了本文方法有效性和效率。

基于共享邻居数的社团结构发现算法

为了快速准确地找到复杂网络的社团结构,提出一种基于共享邻居数和局部模块度的社团结构发现算法。该方法通过不断寻找节点之间的共享邻居数找出与社团连接性最强的节点,并以局部模块度为衡量标准,判断是否将该节点加入到社团中。对3个典型复杂网络的划分结果表明,该算法是可行和有效的。

Wu-Huberman方法和贪婪算法相结合的新聚类算法

将Wu-Huberman算法和贪婪算法思想相结合,提出了一种新的聚类方法。首先应用Wu-Huberman算法计算出网络中各节点的电压值,并在二维坐标系将各个节点表示出来;然后计算各点到坐标原点连线的斜率,将斜率之差最小的节点对合并为中心社团,从中心社团出发,根据合并新社团后的局部模块度变化选择相应的社团进行合并。重复该方法,最终得到原始网络的社团结构划分。实例结果表明了该方法的可行性。

一种基于中心极大团扩展的社区挖掘算法

社区挖掘是复杂网络分析中的一项重要工作,目前已提出多种社区挖掘算法,但多数算法是通过节点间的连接关系来发现内聚的社区结构。结合真实网络中的节点具有不同的行为和影响力,在充分考虑网络中节点的连接关系的基础上,提出一种基于中心极大团扩展的社区挖掘两阶段算法。第一阶段发现初始社区:首先找到网络中所有的内聚子团,然后找出k个分散、内聚且有影响力的中心极大团作为初始社区;第二阶段形成最终社区划分:对初始社区外节点,充分考虑不同邻居节点对其潜在的影响力,采用局部模块度扩展的方法将节点扩展到与其连接紧密的社区内。实验结果表明,该方法能够快速揭示出网络中的社区结构,相比FN算法,具有较高的准确度和模块度,相比GN算法,不需要预先知道社区个数。

基于复杂网络的社区发现算法

针对现有社区发现算法准确度较低的问题,该文提出了1种基于中心节点的社区发现算法。通过各节点度数及节点间相似度寻找社区的中心节点,然后利用局部模块度对各个社区进行优化,并根据节点吸引力将孤立节点和重叠社区节点尽量归入其社区,从而获得整个网络的社区划分。将该文算法分别与3种局部社区发现算法、4种全局社区发现算法相比较,实验结果表明,该算法可以提高社区发现的准确度,具有可行性。

基于社区挖掘的配电网分区重构及储能配置方法

目前电网分区多依靠行政规划和运维人员经验,为此,提出了一种基于局部模块度和差异哈希的社区挖掘算法,将配电网拓扑结构和节点负荷数据联合起来进行社区挖掘。首先将实际采集的配电网历史数据分配到IEEE 33节点系统中的各个节点,建立配电网研究模型。然后,将节点的负荷数据转换成图像,利用社区挖掘算法分析图像间的相似度,实现对配电网的分区,采用模块度对算法的效果进行评估,结果表明该算法效果良好,具有较高的可行性。最后利用社区挖掘的分区结果进行配电网重构,重构后的社区数量明显减少,同时分区间用电负荷的平衡性增强;另外,在社区挖掘后的分区中的关键节点处加入储能装置,发现负荷节点的单日压差减小。

基于超像素合并的高光谱图像分类

超像素级的高光谱图像分类是一类有代表性的谱-空分类方法.与像素级分类方法相比,超像素级的分类方法在分类精度和分类效率方面都有明显的优势.然而,超像素级分类算法的主要缺点是分类结果严重依赖于超像素的分割尺度.已有的工作表明,最优超像素分割尺度的获得往往是一个实验结果,很难预先确定.为了削弱这种依赖性,文章提出了一种基于超像素合并的超像素级高光谱分类算法.该方法首先采用局部模块度函数对所构造的稀疏加权超像素图进行合并;然后通过新定义的映射将每一个超像素块表示为一个样本点,使用流行的KNN方法对合并后的超像素图像进行超像素级分类.超像素的合并增强了空间信息在分类中的作用,有效地削弱了分类结果对超像素分割尺度的依赖性,并提高了分类精度.为了评价该方法的有效性,在4个公开的实际高光谱数据集上,将所提出的方法与一些竞争性的高光谱图像分类方法进行了实验和对比.实验结果和比较结果表明,该方法不仅有效削弱了超像素分割尺度对分类结果的影响,且在分类精度和计算效率方面都有十分明显的优势.