共查询到19条相似文献,搜索用时 125 毫秒
1.
社团结构是复杂网络最普遍和最重要的拓扑属性之一,社团结构的划分方法对分析复杂网络相关统计特性具有十分重要的理论意义.为了提高社团划分精度,提出了一种新的基于信息熵(information entropy)模块度的社团划分算法(简称IE算法).在有着确定社团结构的数据集和不确定社团结构的数据集上,通过选取Q值、社团划分个数、社团最大连通分量大小和强弱社团个数比例4个重要参数,将IE算法与两种最主要的基于模块度的划分算法GN(Girvan-Newman)和FastGN(Fast Girvan-Newman)进行对比,实验结果证明了IE算法在社团划分性能上优于GN和FastGN;将IE和其他7种最主要的经典社团算法进行时间复杂度分析,并在随机网络和真实网络上进行实验,结果表明该算法时间复杂度在GN与FastGN之间,时间复杂度小于GN而精确度优于GN,证明了在大多数数据集上IE算法的社团划分准确度优于传统基于点边比率的社团划分算法的准确度. 相似文献
2.
3.
4.
基于K-means聚类算法的复杂网络社团发现新方法 总被引:4,自引:3,他引:1
提出了一种基于K-means聚类算法的复杂网络社团结构划分方法。算法基于Fortunato等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k个社团,然后通过模块度来确定网络理想的社团结构。该算法有效地避免了K-means聚类算法对初始化选值敏感性的问题。通过Zachary Karate Club和College Football Network两个经典模型验证了该算法的可行性。 相似文献
5.
基于K means聚类算法的复杂网络社团发现新方法* 总被引:1,自引:0,他引:1
提出了一种基于Kmeans 聚类算法的复杂网络社团结构划分方法。算法基于Fortunato等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k个社团,然后通过模块度来确定网络理想的社团结构。该算法有效地避免了Kmeans 聚类算法对初始化选值敏感性的问题。通过Zachary Karate Club和College Football Network两个经典模型验证了该算法的可行性。 相似文献
6.
为了对可以反映网络结构局部重要性质的加权网络进行社团结构划分,延续广泛应用的社团结构分级聚类方法,改进Newman贪婪算法(CNM算法)。算法设计中引入点权和边权,并重新定义新的Q函数计算社团模块度,通过寻找Q函数峰值确定社团划分的最终结果。另外以股票价格波动相关性为加权边建立的加权网络为例进行算法检验,社团划分的结果验证了改进的CNM算法的有效性。与改进的GN算法、极值优化算法等划分效果进行比较分析后发现,改进算法在划分准确性及算法复杂度等方面都有明显的优势。 相似文献
7.
针对现有的产品结构模块划分方法的不足,将复杂网络理论中的社团结构
发现方法应用于产品结构模块的划分,提出了一种新的结构模块划分方法。产品的结构单元
作为网络的节点,有关联的结构单元对应的节点之间为网络的边,从而构建产品结构的网络
图,使用复杂网路理论中的社团结构发现方法—— GN 算法实现结构模块的划分。论文阐述
了基于GN 算法的模块划分的方法与步骤,在此基础上以汽车发动机的结构模块划分为例验
证了该方法的有效性和实用性,并对模块划分结果进行了分析,最后指出了今后进一步研究
的内容与方法。 相似文献
8.
对现有的社会网络社团发现算法进行研究,发现存在算法时间复杂度高、准确率低和没有充分利用节点属性信息等问题,提出了一种基于节点相似度的社团发现算法以解决这些问题。综合考虑图的拓扑结构和节点属性信息,结合构造属性扩展图的思想和基于结构情境相似度的思想得到节点的相似度,利用改进的K-means算法对所有节点进行聚类得到社团结构。编程实验结果表明,使用该算法得到的社团准确率较高,算法的时间复杂度为线性的,在带属性的数据集上和不带属性的数据集上的测试结果均验证了算法的有效性。 相似文献
9.
针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN。算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,因此节点可以被划分到不同的社区,从而发现重叠社区。EGN算法首先需要构造网络节点之间连边关系的边图;然后根据边图中节点的关系计算网络图中连边的相似度,在节点之间相似度的基础上提出了连边之间相似度的计算方法;再按照相似度由小到大对边图删除边,构建出边图的树状图。树状图的每一层对应网络的一个划分,采用划分密度函数来衡量划分的质量,以此寻找最优的划分。最后将算法应用到Zachary空手道俱乐部网络中,并与GN算法进行对比,实验结果表明EGN算法能够很好地发现重叠社区。 相似文献
10.
发现社团结构是研究复杂网络的重要前提,目前社团发现算法研究存在两个较为严峻的问题:评价函数单一和经典算法时间复杂度过大并且无法发现小粒度的社团。针对上述问题,本文首先提出了一种合理的发现算法评价函数,即社团完整度,实验证明,与经典的模块度函数 相比,社团完整度函数能够更合理地评价社团划分质量且社团完整度函数的灵敏度高于模块度函数;其次,本文提出了基于社团密度的社团发现算法,实验证明,该算法不仅可以发现小粒度的社团结构,随着网络节点数和边数的增加BDA算法在时间复杂度方面也具有明显的优势。最后,本文尝试将BDA算法应用在科学合作者网络并得到合理的社团结构。 相似文献
11.
一种网络社团划分的评价及改进方法 总被引:1,自引:0,他引:1
主要从节点在所属群体内的相对重要程度出发, 尝试性地给出一种网络社团结构的新定义, 并在此基础上构建了一种网络社团划分的评价及改进方法。该方法既可以与现有的社团划分算法进行组合, 形成新的网络社团划分算法, 也可以独立使用, 对网络社团的划分结果进行评价与改进。最后, 通过MCL、GN、Factions等方法及算例对提出的算法进行了验证与分析。 相似文献
12.
13.
社区发现是社会网络分析的一个基本任务,而社区结构探测是社区发现的一个关键问题。将社区结构中的结点看作信号源,针对信号传递过程中存在信号缺失情况,提出了一种层次聚类社区发现算法。该算法通过度中心性来度量节点接收信号的概率,用于量化节点接受信号过程中的缺失值。经过信号传递,使网络的拓扑结构转化为向量间的几何关系,在此基础上,使用层次聚类算法用于发现社区。为了验证SMHC算法的有效性,通过在三个数据集上与SHC算法、CNM算法、GN算法、Similar算法进行比较,实验结果表明,SMHC算法在一定程度上提高了社区发现的正确率。 相似文献
14.
针对社会网络中存在较多以度中心节点为中心并且具有多社区重叠节点的网络社区结构,提出了一种面向度中心性及重叠网络社区的两阶段发现算法。第一阶段发现初始社区:选取度最大的Top-k个节点作为候选中心节点,并将每个节点与其邻居节点形成候选初始社区,其中如果某候选社区与已形成的初始社区的重叠度低于阈值,则形成一个新的初始社区;第二阶段调整社区划分:通过偏离度机制进行调整,将偏离度最大值对应的节点划分到连接紧密的相应社区内,形成最终社区划分。实验表明,该方法不仅能够揭示网络中以某个节点为中心的密集的社区结构,还能有效处理初始社区不同程度的重叠问题。相比现有算法,所提方法对预先输入的候选初始社区数k值不敏感,并具有较高的准确性和灵活性。 相似文献
15.
基于节点的中心度和节点对社区的适应度,提出了一种新的重叠社区发现算法。该算法以中心度很大的节点作为初始社区,然后访问社区的邻居节点,把对社区适应度最大的节点加入到社区。如果节点对多个社区都具有很大的适应度,则这些节点归属于多个社区。考虑到社区之间的重叠性,将社区相似度很大的社区合并为一个社区。将该算法应用到Zachary空手道俱乐部网络和海豚社会网络中,实验表明该算法能够很好地划分出网络中的重叠社区。 相似文献
16.
基于三支决策理论,提出了一种基于三支决策的非重叠社团划分算法(N-TWD),该方法将初始聚类形成的重叠社团进行二次划分以形成最终的非重叠社团。N-TWD算法首先利用层次聚类形成有重叠的社团结构,将两个存在重叠的社团的左边社团中非重叠部分定义为正域,右边社团中非重叠部分定义为负域,而两个社团的重叠部分定义为边界域。然后,针对边界域中的节点,分别计算边界域中节点与正域和负域的社团归属度BP、BN进行二次划分。对于二次划分后仍然留在边界域中的节点将利用投票的方法决定其最终归属,最终获得非重叠的社团结构。本文选取4个经典社交网络数据集和1个真实世界数据集对N-TWD算法进行了验证,相比较其他社团划分算法(GN、NFA、LPA、CACDA),N-TWD时间复杂度较低,总体获取的社团模块度值更高。 相似文献
17.
18.
传统社区挖掘算法根据静态的网络拓扑结构进行分析,忽视了个体能动性对网络的影响。针对社会网络中的特殊节点进行研究,引入社区种子和联系者的概念,从个体主义和结构主义两个方面分析社会网络的形成与演化机制,提出了一种基于角色划分的动态社区挖掘算法。在人工网络和真实世界网络上进行了多次测试,并与G-N、快速G-N、Polish等算法进行了比较,结果表明,该算法明显优于G-N算法,且其挖掘到的社区都是强连通社区,具有较好的适应性和可扩展性。 相似文献
19.
结构洞是社会网络中的关键位置,对信息扩散起中介作用。为高效、准确地辨识具有社团结构的社会网络中占据结构洞的节点,提出了一种基于重叠社区和结构洞度的结构洞识别算法,旨在找到一组最具信息优势和控制优势的节点。基本思想是首先定位社区之间的重叠节点,然后利用节点的邻接差异和连接的社区差异衡量其非冗余性,计算出重叠节点的结构洞度,通过对结构洞度值升序排列发现占据结构洞的节点集。应用于实际数据集的实验结果表明,与网络约束系数算法、中介中心度算法、MaxD算法相比,该算法的识别准确度最高,时间复杂度最低。 相似文献