图聚类可以发现网络中的社区结构,是复杂网络分析中的一项重要任务。针对不同节点的聚类难度各异的问题,提出了一种基于节点聚类复杂度的图聚类算法(Graph Clustering Algorithm Based on Node Clustering Complexity,GCNCC),用于判断...图聚类可以发现网络中的社区结构,是复杂网络分析中的一项重要任务。针对不同节点的聚类难度各异的问题,提出了一种基于节点聚类复杂度的图聚类算法(Graph Clustering Algorithm Based on Node Clustering Complexity,GCNCC),用于判断节点的聚类复杂度,为聚类复杂度低的节点赋予伪标签,利用伪标签提供的监督信息降低其他节点的聚类复杂度,进而得到网络聚类结果。GCNCC包括节点表示、节点聚类复杂度判别和图聚类3个主要模块。节点表示模块得到保持网络集聚性的表示;节点聚类复杂度判别模块用于判断网络中的低聚类复杂度节点,并利用低聚类复杂度节点的伪标签信息来优化更新网络中其他节点的聚类复杂度;图聚类模块采用标签传播方法,将低聚类复杂度节点标签传播给高聚类复杂度节点,以得到聚类结果。在3个真实的引文网络和3个生物数据集上与9种经典算法进行对比,算法GCNCC在ACC,NMI,ARI和F1等方面均表现良好。展开更多
图聚类算法可以用于发现社会网络中的社区结构、蛋白质互作用网络中的功能模块等,是当前复杂网络研究的热点之一.对网络中节点的相似性和簇发现结果进行合理度量是核心问题.针对此问题,给出了一种基于节点间点不重复路径度量的节点相似...图聚类算法可以用于发现社会网络中的社区结构、蛋白质互作用网络中的功能模块等,是当前复杂网络研究的热点之一.对网络中节点的相似性和簇发现结果进行合理度量是核心问题.针对此问题,给出了一种基于节点间点不重复路径度量的节点相似性指标.以此为基础提出了一种面向复杂网络的基于“中心-扩展”策略的图聚类算法(A Graph Clustering Algorithm Based on Local Paths between Nodes in Complex Networks,PGC),包括节点相似性计算、中心节点选择、初始簇划分和簇优化四个主要过程.采用点不重复路径对节点相似性进行度量,消除了由大度节点引起较多的点重复路径对节点相似性的影响,提高了算法对大度节点邻域中节点的划分能力.通过与一些经典算法在11个真实网络、22个人工网络数据集上的实验比较分析,结果表明算法PGC在标准互信息、调整兰德系数、F度量、准确度等方面均表现出良好的性能.展开更多
蛋白质互作用网络是一种典型的复杂网络,呈现了明显的社区结构。网络中的社区对应于功能模块,通常被看作蛋白质复合物。蛋白质复合物识别对预测蛋白质功能,解释特定生物进程具有重要作用。基于种子节点扩展的图聚类方法在蛋白质复合物...蛋白质互作用网络是一种典型的复杂网络,呈现了明显的社区结构。网络中的社区对应于功能模块,通常被看作蛋白质复合物。蛋白质复合物识别对预测蛋白质功能,解释特定生物进程具有重要作用。基于种子节点扩展的图聚类方法在蛋白质复合物识别中应用广泛。针对此类算法最终结果受种子节点的影响较大,并且在簇的形成过程中搜索空间有限等问题,提出了一种基于遗传算法的蛋白质复合物识别算法GAGC(genetic algorithm based graph clustering),其中个体表示聚类结果(类别之间可能存在重叠节点),以F-measure值作为种群进化的目标函数。算法采用IPCA(improvement development clustering algorithm)算法产生初始种群;针对初始种群,设计了染色体对齐方式以进行交叉操作产生下一代种群。通过与DPClus、MCODE、IPCA、Cluster One、HC-PIN、CFinder等经典算法的对比实验表明,GAGC算法能够扩大图聚类算法的搜索空间,提高解的多样性,进而提高蛋白质复合物检测的性能。展开更多
复杂网络规模的增大导致网络中社区结构变得复杂,节点与社区之间的关系更多样化,有效度量大规模网络中节点邻域的社区构成,并对社区归属确定性有差异的节点分别进行处理,可以提高算法的社区发现质量。基于此,提出了一种基于节点稳定性...复杂网络规模的增大导致网络中社区结构变得复杂,节点与社区之间的关系更多样化,有效度量大规模网络中节点邻域的社区构成,并对社区归属确定性有差异的节点分别进行处理,可以提高算法的社区发现质量。基于此,提出了一种基于节点稳定性和邻域相似性的社区发现算法(Node Stability and Neighbor Similarity Based Community Detection Algorithm, NSNSA)。首先定义节点的标签熵并对节点在社区发现过程中的稳定性进行度量,选择标签熵较低的节点作为稳定节点集;其次根据节点邻域的标签构成情况定义节点的邻域相似性,对节点与其邻居节点的社区归属一致性进行度量;然后利用稳定节点与其直接邻居中邻域相似性最高的节点构造初始网络,并在该子网络上运行标签传播算法,以得到可靠性较高的初始社区发现结果;最后将未聚类节点分配至与其Katz相似性最高的节点所在的社区,对小规模社区进行合并处理,以得到最终的社区划分结果。在真实网络及人工网络数据集上,与LPA,BGLL,Walktrap, Infomap, LPA-S等经典社区发现算法的对比实验表明,NSNSA算法在模块度以及标准互信息方面表现良好。展开更多
针对基于随机游走的节点相似性度量模型中存在的大度节点依赖问题,从信息论的角度提出了一种改进的随机游走节点相似性度量方法:基于相对熵的随机游走相似性度量方法RE model(A random walk similarity measure model based on Relative...针对基于随机游走的节点相似性度量模型中存在的大度节点依赖问题,从信息论的角度提出了一种改进的随机游走节点相似性度量方法:基于相对熵的随机游走相似性度量方法RE model(A random walk similarity measure model based on Relative Entropy).首先根据随机游走模型得到网络中节点的转移概率向量,再计算两个节点转移概率向量的相对熵得到该节点对的相似性.由于转移概率向量给出了从一个特定节点出发经过多步随机游走后到达网络其他所有节点的概率,导致网络中的每个节点在计算相对熵的过程中都被等同看待,并且网络规模的增大会使计算得到的节点间相似性耗时更多且存在较大偏差.根据节点经过多步随机游走后到达网络中影响力较大的节点的转移概率来构造该节点的转移概率分布,计算两个节点的转移概率分布的相对熵以得到网络中节点对之间的差异分数,进而得到网络节点间的相似性矩阵.RE model度量方法降低了传统随机游走相似性度量对于大度节点的依赖性.通过在真实网络数据集上的实验表明,RE model算法在对称性、网络传播及社区发现等方面表现良好.展开更多
近年来,生成图模型在复杂网络研究中的作用越来越重要。图的生成过程对于研究疾病的蔓延和信息的传播具有重大意义,同时图模型的生成也有助于更深入地研究复杂网络的特性。为了能够生成既符合真实网络特征又具有结构多样性的复杂网络,...近年来,生成图模型在复杂网络研究中的作用越来越重要。图的生成过程对于研究疾病的蔓延和信息的传播具有重大意义,同时图模型的生成也有助于更深入地研究复杂网络的特性。为了能够生成既符合真实网络特征又具有结构多样性的复杂网络,提出了一种具有社区结构的可调节聚集系数和模块性的无标度网络生成算法——TCMSN(Scale Free Network with Tunable Clustering Coefficient and Modularity)。通过调节混合参数可以调节生成网络的模块性,通过调节社区内连边的概率和混合参数可以对网络聚集系数进行调节。TCMSN采用了合理的连边策略,在不破坏网络结构多样性的情况下,能尽可能维持网络的无标度特性。人工构造数据和真实网络数据的对比实验结果表明,TCMSN算法能够生成可调节聚集系数和模块性的无标度网络模型,且能够生成最接近真实网络社区结构特征的网络模型。展开更多
针对标签传播社区发现算法在节点更新顺序及标签传播过程中存在较大随机性而导致划分结果稳定性差的问题,提出一种基于标签传播的两阶段社区发现算法(a two-stage community detectionalgorithm based on label propagation,LPA-TS),通...针对标签传播社区发现算法在节点更新顺序及标签传播过程中存在较大随机性而导致划分结果稳定性差的问题,提出一种基于标签传播的两阶段社区发现算法(a two-stage community detectionalgorithm based on label propagation,LPA-TS),通过参与系数确定节点更新顺序,并在标签传播过程中依据节点间相似性更新节点标签,得到初始社区划分.将社区看作节点,社区间连边数作为边权重,得到社区关系网络.按照参与系数由低到高的顺序合并社区关系网络中的节点,得到最终社区划分结果.算法LPA-TS减少了传统LPA方法在节点更新和标签传播过程的随机性;在第2阶段,将不符合弱社区定义的初始社区与连边最多的相邻社区合并,再按照社区参与系数由低到高的顺序合并初始社区提升社区发现质量.通过与一些经典算法在8个真实网络及不同参数下LFR benchmark人工网络数据集上的实验比较表明LPA-TS算法表现了良好的稳定性,在NMI、ARI、模块性等方面表现良好.展开更多
文摘图聚类可以发现网络中的社区结构,是复杂网络分析中的一项重要任务。针对不同节点的聚类难度各异的问题,提出了一种基于节点聚类复杂度的图聚类算法(Graph Clustering Algorithm Based on Node Clustering Complexity,GCNCC),用于判断节点的聚类复杂度,为聚类复杂度低的节点赋予伪标签,利用伪标签提供的监督信息降低其他节点的聚类复杂度,进而得到网络聚类结果。GCNCC包括节点表示、节点聚类复杂度判别和图聚类3个主要模块。节点表示模块得到保持网络集聚性的表示;节点聚类复杂度判别模块用于判断网络中的低聚类复杂度节点,并利用低聚类复杂度节点的伪标签信息来优化更新网络中其他节点的聚类复杂度;图聚类模块采用标签传播方法,将低聚类复杂度节点标签传播给高聚类复杂度节点,以得到聚类结果。在3个真实的引文网络和3个生物数据集上与9种经典算法进行对比,算法GCNCC在ACC,NMI,ARI和F1等方面均表现良好。
文摘图聚类算法可以用于发现社会网络中的社区结构、蛋白质互作用网络中的功能模块等,是当前复杂网络研究的热点之一.对网络中节点的相似性和簇发现结果进行合理度量是核心问题.针对此问题,给出了一种基于节点间点不重复路径度量的节点相似性指标.以此为基础提出了一种面向复杂网络的基于“中心-扩展”策略的图聚类算法(A Graph Clustering Algorithm Based on Local Paths between Nodes in Complex Networks,PGC),包括节点相似性计算、中心节点选择、初始簇划分和簇优化四个主要过程.采用点不重复路径对节点相似性进行度量,消除了由大度节点引起较多的点重复路径对节点相似性的影响,提高了算法对大度节点邻域中节点的划分能力.通过与一些经典算法在11个真实网络、22个人工网络数据集上的实验比较分析,结果表明算法PGC在标准互信息、调整兰德系数、F度量、准确度等方面均表现出良好的性能.
文摘蛋白质互作用网络是一种典型的复杂网络,呈现了明显的社区结构。网络中的社区对应于功能模块,通常被看作蛋白质复合物。蛋白质复合物识别对预测蛋白质功能,解释特定生物进程具有重要作用。基于种子节点扩展的图聚类方法在蛋白质复合物识别中应用广泛。针对此类算法最终结果受种子节点的影响较大,并且在簇的形成过程中搜索空间有限等问题,提出了一种基于遗传算法的蛋白质复合物识别算法GAGC(genetic algorithm based graph clustering),其中个体表示聚类结果(类别之间可能存在重叠节点),以F-measure值作为种群进化的目标函数。算法采用IPCA(improvement development clustering algorithm)算法产生初始种群;针对初始种群,设计了染色体对齐方式以进行交叉操作产生下一代种群。通过与DPClus、MCODE、IPCA、Cluster One、HC-PIN、CFinder等经典算法的对比实验表明,GAGC算法能够扩大图聚类算法的搜索空间,提高解的多样性,进而提高蛋白质复合物检测的性能。
文摘复杂网络规模的增大导致网络中社区结构变得复杂,节点与社区之间的关系更多样化,有效度量大规模网络中节点邻域的社区构成,并对社区归属确定性有差异的节点分别进行处理,可以提高算法的社区发现质量。基于此,提出了一种基于节点稳定性和邻域相似性的社区发现算法(Node Stability and Neighbor Similarity Based Community Detection Algorithm, NSNSA)。首先定义节点的标签熵并对节点在社区发现过程中的稳定性进行度量,选择标签熵较低的节点作为稳定节点集;其次根据节点邻域的标签构成情况定义节点的邻域相似性,对节点与其邻居节点的社区归属一致性进行度量;然后利用稳定节点与其直接邻居中邻域相似性最高的节点构造初始网络,并在该子网络上运行标签传播算法,以得到可靠性较高的初始社区发现结果;最后将未聚类节点分配至与其Katz相似性最高的节点所在的社区,对小规模社区进行合并处理,以得到最终的社区划分结果。在真实网络及人工网络数据集上,与LPA,BGLL,Walktrap, Infomap, LPA-S等经典社区发现算法的对比实验表明,NSNSA算法在模块度以及标准互信息方面表现良好。
文摘针对基于随机游走的节点相似性度量模型中存在的大度节点依赖问题,从信息论的角度提出了一种改进的随机游走节点相似性度量方法:基于相对熵的随机游走相似性度量方法RE model(A random walk similarity measure model based on Relative Entropy).首先根据随机游走模型得到网络中节点的转移概率向量,再计算两个节点转移概率向量的相对熵得到该节点对的相似性.由于转移概率向量给出了从一个特定节点出发经过多步随机游走后到达网络其他所有节点的概率,导致网络中的每个节点在计算相对熵的过程中都被等同看待,并且网络规模的增大会使计算得到的节点间相似性耗时更多且存在较大偏差.根据节点经过多步随机游走后到达网络中影响力较大的节点的转移概率来构造该节点的转移概率分布,计算两个节点的转移概率分布的相对熵以得到网络中节点对之间的差异分数,进而得到网络节点间的相似性矩阵.RE model度量方法降低了传统随机游走相似性度量对于大度节点的依赖性.通过在真实网络数据集上的实验表明,RE model算法在对称性、网络传播及社区发现等方面表现良好.
文摘近年来,生成图模型在复杂网络研究中的作用越来越重要。图的生成过程对于研究疾病的蔓延和信息的传播具有重大意义,同时图模型的生成也有助于更深入地研究复杂网络的特性。为了能够生成既符合真实网络特征又具有结构多样性的复杂网络,提出了一种具有社区结构的可调节聚集系数和模块性的无标度网络生成算法——TCMSN(Scale Free Network with Tunable Clustering Coefficient and Modularity)。通过调节混合参数可以调节生成网络的模块性,通过调节社区内连边的概率和混合参数可以对网络聚集系数进行调节。TCMSN采用了合理的连边策略,在不破坏网络结构多样性的情况下,能尽可能维持网络的无标度特性。人工构造数据和真实网络数据的对比实验结果表明,TCMSN算法能够生成可调节聚集系数和模块性的无标度网络模型,且能够生成最接近真实网络社区结构特征的网络模型。
文摘针对标签传播社区发现算法在节点更新顺序及标签传播过程中存在较大随机性而导致划分结果稳定性差的问题,提出一种基于标签传播的两阶段社区发现算法(a two-stage community detectionalgorithm based on label propagation,LPA-TS),通过参与系数确定节点更新顺序,并在标签传播过程中依据节点间相似性更新节点标签,得到初始社区划分.将社区看作节点,社区间连边数作为边权重,得到社区关系网络.按照参与系数由低到高的顺序合并社区关系网络中的节点,得到最终社区划分结果.算法LPA-TS减少了传统LPA方法在节点更新和标签传播过程的随机性;在第2阶段,将不符合弱社区定义的初始社区与连边最多的相邻社区合并,再按照社区参与系数由低到高的顺序合并初始社区提升社区发现质量.通过与一些经典算法在8个真实网络及不同参数下LFR benchmark人工网络数据集上的实验比较表明LPA-TS算法表现了良好的稳定性,在NMI、ARI、模块性等方面表现良好.
