基于信号传递与层次聚类的社团发现算法

社团是社会网络的一个重要特征,社团发现是近年来研究的热点问题之一。通过在复杂网络上传递信号,获得各节点对网络的影响向量,从而把网络中节点的拓扑性质转化为代数空间上向量的几何关系,然后用结合模块度的层次聚类挖掘社会网络中的社团结构。该算法优点是不需要预先知道社团的数量或社团内节点的数量,用Zachary空手道俱乐部网络、大学足球赛网络以及海豚关系网络的数据进行验证,该算法划分的社团准确性超过了Newman的结论。     

基于局部相似性的复杂网络社区发现方法

复杂网络是复杂系统的典型表现形式, 社区结构是复杂网络最重要的结构特征之一. 针对复杂网络的社区结构发现问题, 本文提出一种新的局部相似性度量, 并结合层次聚类算法用于社区结构发现. 相对全局的相似性度量, 本文提出的相似性度量具有较低的计算开销; 同时又能很好地刻画网络的结构特征, 克服了传统局部相似性度量在某些情形下对节点相似性的低估倾向. 为了将局部相似性度量用于社区结构发现, 推广了传统的Ward层次聚类算法, 使之适用于具有相似性度量的任意对象, 并将其用于复杂网络社区结构发现. 在合成和真实世界的网络上进行了实验, 并与典型算法进行了比较, 实验结果表明所提算法的可行性和有效性.     

边异质网络中的社区结构发现算法

为解决社区结构发现算法功能社区与拓扑社区不一致的问题,提出一种基于边类型相似性聚类(TESC)的社区结构发现算法。该算法以局部拓扑特征与异质信息为目标进行节点聚类,基于节点邻接边类型构造网络节点之间的相似矩阵,从而获取边异质信息。在该相似矩阵的基础上,通过传统层次聚类的思想将相似度大的节点进行合并,进而利用轮廓系数优化社区数量,得到最终社区划分结果。选取社区结构已知的4个真实网络和6个人工合成基准LFR网络,通过与同质网络的GN、Louvain算法以及异质网络的Hete-SPAEM、Hetero-Attractor算法对比,结果表明TESC算法获得的社区结构更接近于网络实际社区结构。     

基于信号自适应传递的社团发现算法

为了准确地检测出复杂网络的社团结构,提出一种基于信号自适应传递的社团发现方法。首先使信号在复杂网络上自适应地传递,从而获取网络中各节点对整个网络的影响向量,然后把网络中节点的拓扑结构转化成代数向量空间上的几何关系,最后结合聚类特性发现网络中的社团结构。为获取更加合理的空间向量,提出最佳传递次数,缩小搜索空间,增强算法寻优能力。该算法在计算机生成网络、Zachary网络和美国大学生足球赛网络上进行实验测试, 并与GN算法、谱聚类算法、极值优化算法和信号传递算法进行实验对比,社团划分的准确性和精确性均有所提高,证明该算法具有有效性和可行性。     

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

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

基于加权聚类集成的标签传播算法

标签传播算法（LPA）是一种高效地处理大规模网络的社区发现算法,由于其近乎线性的时间复杂度而受到广泛关注。然而,该算法每个节点的标签依赖于其邻居节点,其迭代速度和聚类有效性对标签信息的更新顺序非常敏感,影响了社区发现结果的准确性和稳定性。基于该问题,提出了一种基于加权聚类集成的标签传播算法。该算法利用多次标签传播算法的结果作为基聚类集,并用模块度评估每个基聚类的重要性,使其作为节点相似性度量的权值形成加权相似性矩阵,最后通过层次聚类得出最终的社区划分结果。在实验分析中,该算法和其他5个具有代表性的标签传播算法的改进算法在真实数据集上进行了比较,展示了新算法能有效地提高标签传播算法的社区发现精度。     

基于谱聚类的社交网络动态社区发现算法

动态社区发现研究是社交网络分析（SNA）的重要研究领域。随着节点加入或离开社交网络，节点间的关系也随之建立或消失，进而影响着社区结构的变化。针对社交网络静态社区发现算法缺少必要的社区节点历史信息而导致的网络结构分析、聚类信息不足和计算开销过大的问题，基于社区网络演化事件的划分并根据主要社区事件的分析，提出一种基于谱聚类的动态社区发现算法（SC-DCDA）。首先，根据实验观察使用谱映射的方法将高维数据降维，并采用改进的模糊C-均值聚类（FCM）算法确定动态社交网络中的节点与待发现社区的关联度；其次，根据演化相似度矩阵分析社区结构。通过使用真实网络数据集以及模块度得分、轮廓系数等社区发现算法衡量指标，评估所提算法的效果。实验结果表明，SC-DCDA的计算开销相较于传统谱聚类降低了8.37%，在所有数据集上的平均模块度得分是0.49，其他衡量指标的定性分析结果也较好，验证了所提算法在信息交互、聚类效果和精确度上表现较好。     

用于网络重叠社区发现的粗糙谱聚类算法

针对绝大多数社区发现算法都存在着网络节点仅隶属于一个社区的假设,引入谱图理论与粗糙集理论来分析复杂网络社区,提出一种用于网络重叠社区发现的粗糙谱聚类算法RSC,该算法用上下近似来刻画网络节点的社区归属,边界表示社区之间共享的节点,通过优化重叠社区结构模块度来实现重叠社区发现.通过3个不同类型真实网络的仿真实验,结果验证了该方法的可行性与有效性.     

基于最大团的层次化重叠社区发现算法

研究表明,很多真实网络具有层次结构和重叠结构。传统的层次聚类算法通常以节点为对象进行扩展形成层次树图从而得到网络的层次结构。这种做法存在两个问题,其一是算法的稳定性,主要体现在初始节点的选择上,少数情况下,初始节点的不同会导致算法最终结果的不同,即使算法的结果不依赖于初始节点,但算法的复杂度会随之变化;其二是不能发现网络中的重叠结构。针对以上问题,提出一种基于最大团的层次化重叠社区发现算法。该算法以最大团为扩展对象,然后利用最大团扩展策略生成层次树图,最后采用重叠模块度函数对层次树图进行剪枝得到社区划分结果。在真实网络以及LFR人工网络上的实验结果表明该算法能够有效地挖掘网络中的层次结构和重叠结构。     

基于节点聚类复杂度的图聚类方法

图聚类可以发现网络中的社区结构，是复杂网络分析中的一项重要任务。针对不同节点的聚类难度各异的问题，提出了一种基于节点聚类复杂度的图聚类算法(Graph Clustering Algorithm Based on Node Clustering Complexity, GCNCC),用于判断节点的聚类复杂度，为聚类复杂度低的节点赋予伪标签，利用伪标签提供的监督信息降低其他节点的聚类复杂度，进而得到网络聚类结果。GCNCC包括节点表示、节点聚类复杂度判别和图聚类3个主要模块。节点表示模块得到保持网络集聚性的表示；节点聚类复杂度判别模块用于判断网络中的低聚类复杂度节点，并利用低聚类复杂度节点的伪标签信息来优化更新网络中其他节点的聚类复杂度；图聚类模块采用标签传播方法，将低聚类复杂度节点标签传播给高聚类复杂度节点，以得到聚类结果。在3个真实的引文网络和3个生物数据集上与9种经典算法进行对比，算法GCNCC在ACC,NMI,ARI和F1等方面均表现良好。     

Study on the algorithm for smart community sensor network routing with adaptive optimization via cluster head election

To reduce the uneven energy consumption for the data transmission and extend network life of intelligent community sensor network, an adaptive routing optimized algorithm for intelligent community sensor networks with cluster head election is proposed. In this algorithm, a three-dimensional clustering method adapted to the structure of intelligent community sensor network is proposed. The three-dimensional clustering method uses the cluster head election mechanism based on minimizing the total transmission loss to optimize the energy of the intelligent community sensor network. Second, an adaptive ant colony propagation method is proposed to solve the problem of intercluster data propagation after clustering. With the best path finding algorithm of ant colony algorithm, energy balance routing with lower energy loss and lower packet error rate is proposed. Finally, the simulation results show that the algorithm has better performance in reducing energy consumption and delay, improving transmission efficiency and node survival time.     

植入引导式层次聚类Mashup服务推荐算法*

针对传统Mashup服务推荐算法在关键字聚合搜索和网络构建等方式中计算复杂度过高的问题,提出一种基于语义标签的植入引导式层次聚类Mashup服务推荐算法。首先,为提高聚类算法的收敛精度,提高算法运行效率来满足大型数据搜索对算法简化的需求,采用数据预处理和植入易于获取具有代表性的样本数据对聚类进行引导,防止层次聚类算法顶层集分类失败导致的算法聚类失败。其次,利用改进的聚类算法结合实际的Mashup服务数据库,设计了植入引导式层次聚类Mashup服务推荐算法。最后,通过通过仿真对比表明,基于语义的植入式半监督层次聚类Mashup服务推荐算法的精度要好于对比算法,验证所提算法的有效性。     

一种基于节点特征向量的复杂网络社团发现算法

社团结构是复杂网络的一种很普遍且非常重要的拓扑特征,社团的发现有助于了解复杂网络的结构和功能。节点间相似度的评价指标对于社团发现的结果起着至关重要的作用,传统算法中使用的相似度指标存在着时间复杂度过高和不够精确的缺陷。为了弥补这两个缺陷,在信息传递理论的基础上将网络中的节点抽象成了多维数据集,结合传统聚类算法K-means提出了一种社团发现的新算法。基于Zachary Karate Club网络、Jazz Musician网络和Facebook网络的实验结果表明,该算法是高效且准确的。     

基于桥系数的分裂社区检测算法研究

研究社区结构有助于揭示网络结构和功能之间的关系,而社区检测是社区结构研究的基础和核心。该文定义了一种聚集度桥系数,将其应用到社区检测中,设计出一种分裂社区检测方法,包括分裂和合并两个算法。分裂算法使用桥系数识别社区间边,通过迭代删除社区间边分解网络,从而发现网络中的社区结构;合并算法根据社区连接强度合并社区,可以揭示社区结构中的分层嵌套的现象。在六个社会网络数据集上的实验表明,本文算法可以有效的将网络分裂为有意义的社区,并且准确性接近或超过经典的社区检测算法。     

从链接密度遍历序列中挖掘网络社团的层次结构

提出一种称为TRAVEL的网络聚类算法.它能够产生包含所有可能密度聚类的网络链接遍历序列,并从中自动发现网络的全局优化聚类.然后,遍历序列被转挟为连续子区间堆结构.在此基础上,提出一种聚类算法HCLU,可以无须用户干预地从连续子区间堆中自动发现网络的层次聚类边界.在真实网络以及计算机生成的仿真网络数据集上的实验结果表明...     

复杂网络聚类特征层次布局算法

网络聚类模式发现是网络分析中的一项重要任务,好的网络布局应能体现网络中的聚类特征,并允许用户从不同层次探索网络结构。为此,基于社团划分和多层次布局思想提出了聚类特征层次布局算法。首先利用种子节点和个性化PageRank对网络实现社团划分;其次根据划分结果对网络进行粗化,并设计了粗化网络初始布局;然后利用节点度信息改进力导向模型以完成细化;最后,为验证所提算法的有效性,设计了从整体到局部的实验。实验表明所提算法能够在有效时间内生成高质量的布局结果,与现有布局算法相比,所提算法更能真实展示网络聚类特征,同时兼顾网络微观结构,能够满足用户从不同层次探索网络结构的需要。     

加权Fast Newman模块化算法在人脑结构网络中的应用

针对二值人脑结构网络的模块化方法不足以反映复杂的人脑生理特征这一问题,提出一种基于Fast Newman二值算法的加权脑网络模块化算法。该算法以凝聚节点的层次聚类思想为基础,以脑网络中单个脑区节点的权重值和脑网络总权重值为主要依据构建加权模块度评价指标,并将其增量作为度量值来确定加权脑网络中节点的合并从而实现模块划分。将该算法应用于60个健康人的组平均数据中的实验结果显示,与二值人脑网络模块化结果相对比,所提算法得到的模块度提高了28%,并且模块内部和模块外部的特征区分更加明显,所得到的人脑模块也更符合已知的人脑生理特性;而与现有的两种加权模块化算法实验对比结果表明,所提算法在合理划分人脑网络模块结构的同时也小幅提高了模块度。