复杂网络中的层次结构挖掘

挖掘复杂网络中的层次结构对复杂网络的研究有着重要的意义.复杂网络中的社团结构往往具有层次性.过去的研究中,研究者更多的关注于层次社团结构,而很少关注于社团内部成员的层次结构.因此,提出一种基于模糊相容关系的层次结构挖掘算法(fuzzy tolerance relation based hierarchical structure detection algorithm,FHSD),旨在挖掘层次社团结构以及社团内部成员层次结构.在该算法中,首先通过相似度函数计算节点之间的相似性从而获取一个满足模糊相容关系的相似度矩阵;其次,基于相似度矩阵获取对应的商空间链;然后,依据重叠节点对各社团的隶属度处理商空间链各层中的重叠节点,从而得到层次社团结构;最后,基于处理后的商空间链,获取对原始模糊相容的近似模糊等价关系,从而获取社团内部成员层次结构.在真实网络上的实验结果表明:(1)复杂网络中不仅存在层次社团结构,同时存在基于模糊相容关系的社团成员层次结构;(2)相比于当前主流的社团挖掘算法,FHSD挖掘出的社团结构具有最高的精准性(NMI accuracy)和较高的模块度值.     

一种基于节点重要度的社团划分算法

指出了通过挖掘复杂网络中存在的社团结构,可以分析整个复杂网络的拓扑结构和功能,还可以发现网络中隐藏的规律.为了得到最佳社团划分结构,定义了网络的节点重要度矩阵和聚类矩阵,结合图的特征谱平分法和模块度函数,提出了一种基于节点重要度的社团划分算法(CDNIM).通过在空手道俱乐部、海豚关系网络等多个经典数据集上应用,结果表明:该算法能够有效提高发现社团结构的准确率.     

基于共邻节点相似度的加权网络社区发现方法

为实现加权网络的准确划分,发现真实的社区结构,提出一种基于模块度和共邻节点相似性的层次聚类社区划分方法IEM.首先,定义两节点间基于共邻节点的相似度.之后,基于该度量快速聚合当前节点和与其关联紧密度最强的邻居节点以形成初始社区,并进行社区扩展.最后,以最大化网络模块度为目标进行社区合并以优化划分结果.算法通过形成初始社区、扩展社区、合并社区三步,实现了加权网络合理有效的社区划分.以加权模块度作为社区划分质量的评价标准,在多个数据集上的实验结果表明,IEM算法优于加权CN、加权AA、加权RA.同时,与CRMA算法相比,IEM算法对加权网络社区划分的有效性和正确性更高.     

基于贝叶斯后验模型的局部社团发现

基于节点的局部社团发现在大数据社会网络分析中非常重要。针对Newman模块度在社团发现中的局限性,基于贝叶斯后验模型提出了BS模块度度量法。该方法结合节点的模块度和推荐概率进行建模,并以邻接并入为框架得到了一种新的局部社团发现算法。该方法克服了Newman模块度在稀疏网络中区分度低的问题以及社团结构差异大的分辨率问题,有效地寻找大规模网络中的局部社团。通过与Newman模块度在真实社团中的比较,验证了该度量方法的有效性。     

基于模块度优化的加权复杂网络社团发现算法分析

社团结构是复杂网络的一种重要拓扑结构。针对加权复杂网络中的社团发现问题,在8个不同领域、不同规模的真实数据集上,从模块度、强/弱社团、聚集系数3个评估指标分析了基于模块度优化的GN算法、FN算法、CNM算法和BGLL算法在加权复杂网络社团发现的效果。研究结果表明,上述3个评估指标在加权复杂网络上的划分结果不能始终保持一致,基于优化模块度的算法更倾向于找到复杂网络中比较粗糙的社团结构,而不是精准的社团结构,其算法的泛化能力有待加强。     

一种基于相似社团和节点角色划分的社交网络用户推荐方案

针对现有的社交网络用户推荐方案中主要考虑个体相似性问题以及节点角色无层次差别的问题,提出一种基于相似社团和节点角色划分的推荐方案。在传统的用户相似度计算基础上,从社团结构和属性两方面,综合考虑社团间联系的紧密程度和社团用户兴趣爱好相似程度,提出一种社团相似度的计算方法;其次,从用户节点所在的社团内部和外部2个维度度量节点间紧密度,并据此度量节点的社会影响力,进而将它们划分成不同角色,实现用户推荐的差异化。通过新浪微博真实社交数据对方案进行验证,实验结果表明,该方案适用于存在社团现象的社交网络层次化用户推荐,并具有良好的推荐效果。     

改进的基于模块度最大化二分图权重网络社团挖掘算法

复杂网络广泛应用于生态学、生物信息学等多个领域,其中加权二分图网络作为一种特殊结构的复杂网络可以用来对许多实际问题进行建模。网络的社团挖掘一直以来都是分析复杂网络的重要手段,也是复杂网络领域研究的热点问题。本文提出了一种改进的模块度最大化二分图权重网络社团挖掘算法,通过在实际网络中的测试,相较于其他的同类型算法,本算法可以得到更好的社团划分结果,其执行效率也明显高于现有的其他算法,可以用于大规模二分图网络的社团挖掘。     

采用链路聚类的动态网络社团发现算法

针对当前基于节点的动态网络社团结构发现算法难以发现稳定的社团结构的问题,提出了一种采用链路聚类的动态网络社团发现算法(LDC)。该算法首先从链路的角度得到网络的链路图结构;然后对比不同时刻的链路图结构,将动态网络中节点的添加与移除以及边的添加与移除等复杂的变化信息简化为链路添加和链路移除2种增量变化信息;再在前一时刻社团结构的基础上以改进的链路划分密度函数对增量变化信息中变化的链路进行处理,判断该链路是否加入到社团中从而得到最优的社团结构;最后将得到的链路社团转化成为最终的节点社团结构。实验结果表明,相比于当前基于节点的动态社团发现算法,LDC算法能够有效地发现网络中结构稳定的社团结构,其模块度值和标准化互信息值至少提高了0.19和0.13,且算法的运行效率要明显优于基于节点的动态社团发现算法。     

一种可变分辨率的社团发现算法

介绍了复杂网络及社团结构的相关概念,给出节点的综合特征值和增益函数的定义,然后提出一种新的社团发现算法(CNCD).综合特征值与节点的度数及其聚类系数有关,用于发现社团中的核心节点;增益函数决定何时获得社团结构的最佳划分.作者用C++语言实现算法,并使用经典数据集对算法进行验证,实验结果表明此算法不仅能够得到正确的社团结构,而且通过动态调整算法中的参数值,能够得到比传统算法更加详细的社团划分结果,获得网络的细节信息.     

具有小世界特性的复杂液压系统故障源搜索方法

针对复杂液压系统故障多样、成因复杂、隐蔽性强,故障源辨识困难,提出了一种基于小世界特性的先网络社团结构划分、后社团内的复杂液压系统故障源搜索的层次分析方法.构建了复杂液压系统的网络拓扑结构,以同时具有大的介数和度数的节点作为网络中故障传播社团的中心,来改进Wu-Huberman算法,从而实现了社团结构的划分.根据各社团连接边对应管路的液压参数变化,确定包含故障源的社团,进一步计算该社团故障传播的可达矩阵,定位了故障源节点.经过对轧钢加热炉液压系统起升故障的分析和故障源查找,证实了该方法可以根据系统网络的结构特征和间接故障表现,实现复杂液压系统故障源的识别.     

基于联合引力度扩展的加权网络重叠社区划分算法

基于引力度扩展的重叠社区发现算法(GDE),主要用于挖掘无权社交网络的重叠社区结构.真实社区更多是具有加权属性的,本文根据 GDE 算法的种子策略思想,并依据加权网络的特征,以网络节点的度与强度来综合确定重叠社区的中心节点,提出基于联合引力度扩展的加权网络重叠社区划分算法(UGDE).算法的实验检测结果表明：该算法对划分加权网络中的重叠社区具有可行性与有效性.     

本体结构与复杂网络的特性相似性研究

以茶树本体为研究对象,对茶树本体中的结构特性进行分析.以本体中的概念为节点,概念间的关系为边,形成本体结构拓扑图.计算节点的度、平均路径长度、聚集系数、介数等参数,得出茶树本体在无向网络的意义下具有无标度特性和小世界特性,从而说明本体结构具有复杂网络特性.这给社团划分及重要概念挖掘等以本体为基础的语义网络研究提供了新的研究方法.     

基于最短路径相似度的复杂网社团识别算法

基于最短路径的思想,定义新的节点相似度,利用谱平分算法来识别复杂网络的社团结构.首先根据节点间最短路径的思想计算改进的共享最近邻(SNN)相似度,将其标准化后求出标准化矩阵的特征值及特征向量,然后根据网络选取一定数目的第一非平凡特征向量作为聚类样本,利用FCM算法可识别网络的社团.实验结果表明,该算法对于社团结构不明显的网络划分效果很好.     

交通运输网络节点重要度评价体系研究

节点重要度评价是交通运输网络规划的基础性工作.交通运输网络是复杂加权网络,它的节点重要度不仅与路网拓扑结构有关,还与阻抗和运输能力密切相关.借鉴复杂网络和通信网络的研究成果,结合交通运输网络特性,提出交通运输网络的节点重要度应该从拓扑结构、最短路径和运输能力三个层次上分析.并根据交通分担率和失效后果来界定节点重要度,分别引入和建立了相应的重要性指标,形成较为完整的评价指标体系.     

电商商品网络的挖掘研究

研究发现,社团结构是复杂网络中的重要特性之一.针对电商数据,文章扩展社团理论提出商品社团:以商品为网络节点,以商品间的相关度作为节点之间是否连接的判断标准,构建商品网络,然后针对该网络进行社团分析,其中,作者采用皮尔森相关系数作为相关度的度量.通过分析天猫的数据,发现商品网络中确实存在社团结构,其中,手机数据中的社团特性更加明显.在各个社团中,通过介数可发现该社团中的重要商品.同时,分析了相关度的度量参数、商品类型和邻接矩阵二值化门限等因素对商品社团结构的影响,以验证所提方法的扩展性.最后,利用所提方法对商品的销售进行了预测,与基于K-means的预测方法相比,平均准确率提高9.5%以上.     

基于最小社团链接度增量的社团结构挖掘算法

针对复杂网络社团结构挖掘算法复杂度高的问题,定义了一个衡量局部社团结构的指标,提出了一种基于最小社团链接度增量的社团结构挖掘算法.本算法的时间复杂度为O(kd),其中d为网络的平均节点度数,k为搜索的节点数.为了验证本算法的性能和计算的准确性,把本算法与一种经典的挖掘局部社团结构方法——Clauset算法,进行了比较.实验结果表明:本算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有了显著提高.     

基于加权中介中心性的结构洞占据者方法获取

随着网络和计算机科学的迅猛发展,处于网络结构洞位置的个人或团体从中可以获得丰富的信息利益和控制利益,结构洞占据者的挖掘得到了越来越多的关注.目前对结构洞占据者的挖掘研究主要集中于无权网络方面,但在实际网络中,权重对网络的性能也起着重要的作用.以加权网络为研究对象,将边权引入到中介中心性指标中,对现有的HIS算法进行改进,提出一种基于加权中介中心性的结构洞占据者挖掘算法(W_BCHIS).该方法首先利用社团发现算法求出加权网络的社团,接着将边权引入中介中心性指标,用加权后的中介中心性指标对节点的重要性进行初始化,通过对节点的重要性和节点占据结构洞的可能性不断地迭代直到收敛以挖掘出结构洞占据者.将W_BCHIS算法与其他算法在公用数据集和实际数据集上进行了实验对比与分析,验证了该算法的有效性.     

基于相邻节点聚类的社团划分算法

社团结构是复杂网络中的拓扑属性之一,具有同一社团内的节点连接紧密而不同社团的节点连接疏松的性质.作者基于复杂网络中的社团结构的性质并根据网络中相邻节点的距离关系,提出了一种社团划分算法--基于相邻节点聚类的社团划分算法.笔者对算法的基本概念以及实现进行了详细的描述,通过应用在实例上所得结果说明算法的可行性.     

一种改进的基于节点相异度的社团结构划分算法

提出一种改进的基于节点相异度的社团结构划分算法.首先根据度和平均度评估标准,筛选出核心节点作为初始核心节点集,然后基于节点相异度进行划分,直至社团结构划分完成.实验结果证明,与其他一些算法相比,该算法的划分效果比较精确且易于实现.     

大规模软件宏观拓扑结构度分布及其演化分析

基于大量开源软件源代码度量数据,根据大规模软件宏观拓扑结构体现出来的复杂网络特征,将软件结构抽象为网络拓扑.在这基础上,采用复杂网络的度量分析方法,分别从无向图网络的度分布和有向图网络的出入度分布两方面讨论了大规模软件宏观拓扑结构度分布所体现出的无尺度特征.认为随着软件演化,度分布系数和入度分布系数呈下降趋势,最大节点入度值则呈增大的趋势;而出度分布系数和最大节点出度值则变化有限.然后结合软件工程实践探讨了上述现象形成原因,认为软件系统其结构还有进一步优化的空间.