一种新的复杂网络聚类算法

揭示网络簇结构的复杂网络聚类方法研究具有重要的理论意义和应用价值。应用两种谱方法将复杂网络簇结构发现问题转换为空间数据聚类问题,并将粒子群聚类算法应用到对复杂网络簇结构的探测,提出了两种新的结合粒子群聚类的复杂网络簇结构探测算法。最后在两类复杂网络上进行实验并对实验结果进行了比较分析,提出的新算法在聚类准确性方面效果更好。     

复杂网络聚类算法在生物网络中的应用

复杂网络在现实世界中普遍存在,具有小世界性和无标度性等统计特性,网络簇结构是复杂网络重要的拓扑属性之一。在复杂生物网络中使用聚类算法揭示生物网络中的簇结构对分析生物网络的拓扑结构、预测其功能都具有重要意义。对复杂网络聚类方法在蛋白质-蛋白质相互作用网络和新陈代谢网络中的应用及其进展情况进行了综述,分析了几种聚类算法的评价函数和适用条件,并对生物网络聚类算法研究所面临的主要问题进行了讨论。     

一种基于数据场的复杂网络聚类算法

针对当前复杂网络研究中聚类的热点问题,提出了一种基于数据场的复杂网络聚类算法,该算法通过一种基于互信息的方法计算出复杂网络中节点的重要性,然后通过数据场中节点的势来划分网络的簇结构。实验证明,该算法在计算时间和精度上具有一定的优势。     

一种改进的加权复杂网络聚类方法

在复杂网络聚类中,为了克服聚类结果局部收敛和对多维数据聚类效果差的缺点,通过对复杂网络聚类方法 的应用分析,将NJ W算法和粒子群聚类算法应用到加权复杂网络簇结构的探测中,设计和实现了一种改进的加权复 杂网络聚类方法。实验验证了该方法在簇结构较复杂的网络中具有较高的执行效率和较好的执行效果。     

移动节点的LEACH改进型算法

LEACH（low-energy adaptive clustering hierarchy）是一种有效延长网络生命周期的通信协议,其组网过程中存在聚类大小范围不定和簇间干扰现象.针对该问题,提出基于移动节点的LEACH改进型算法.节点以一定半径广播成簇消息限定聚类大小,减少簇首通信干扰.针对网络运作一段时间后出现能量过低或者不平衡的聚类,加入移动式感测节点,移动至聚类担任簇首,延长网络生存时间.实验结果与分析表明新方法远好于LEACH.     

复杂网络簇结构探测——基于随机游走的蚁群算法

网络簇结构是复杂网络最普遍和最重要的拓扑属性之一,网络聚类问题就是要找出给定网络中的所有类簇.有很多实际应用问题可被建模成网络聚类问题.尽管目前已有许多网络聚类方法被提出,但如何进一步提高聚类精度,特别是在没有先验知识(如网络簇个数)的情况下如何发现合理的网络簇结构,仍是一个未能很好解决的难题.针对该问题,在马尔可夫随机游走思想的启发下,从仿生角度出发提出一种全新的网络聚类算法——基于随机游走的蚁群算法RWACO.该算法将蚁群算法的框架作为RWACO的基本框架,对于每一代,以马尔可夫随机游走模型作为启发式规则;基于集成学习思想,将蚂蚁的局部解融合为全局解,并用其更新信息素矩阵.通过“强化簇内连接,弱化簇间连接”这一进化策略,使网络簇结构逐渐地呈现出来.实验结果表明,对一些典型的计算机生成网络和真实网络,该算法能够较准确地探测出网络的真实类簇数与一些有代表性的算法相比,具有较高的聚类精度.     

基于聚类分析的复杂网络链路预测性能研究

链路预测问题是复杂网络中数据挖掘领域的重要研究方向,然而复杂网络的结构与预测方法性能之间关系却很少受到关注。从聚类分析的角度探讨复杂网络结构对现有基于相似性度量的六种链路预测方法的性能影响,通过对合成复杂网络和真实复杂网络的对比实验进行分析。结果表明：随着聚类簇的增加,这六种方法在预测精度方面的性能均得到了极大的提升。对于具有较低聚类簇的稀疏复杂网络,叠加随机游动（SRW）预测性能表现最佳,而对于具有较高聚类簇的密集复杂网络,资源分配指数（RA）预测性能表现最佳。因此,对于不同类型的复杂网络应采用不同的方法进行链路预测。     

面向Web网页的区域用户行为实证研究

用户对Web网页的访问是由用户需求行为确定的一个随着时间演化的复杂双模式二分网络.通过对网站聚类生成的二分网络的实证研究表明,其入度分布呈现出典型的无标度特征和集聚现象,幂指数介于1.7到1.8之间.将这种双模式二分网络映射为两种含权单模式网络:用户群体兴趣广义关联网络和网站资源广义关联网络,从而深入研究用户群体行为的关联性和从用户行为角度网站资源的关联性.实证分析其统计特性表明,两者的边权分布是幂律的,网络节点关联紧密且呈现簇聚特征.用户行为的无标度特征和集聚特点对优化Internet网络拓扑结构,改善其网络性能具有重要意义.     

多层无线异质传感网络的高效节能预测聚类算法研究

无线传感网络设计主要是减少能源消耗,延长网络生存时间。介绍了一种异质传感网络应用于现存聚类算法的研究,并提出了一种高效节能的预测聚类算法,此算法能适应能源和目标异质的传感网络。根据各种因素(如能源和通信成本),该算法能使节点选择簇头。相对于具有较低剩余能源的节点,具有较高剩余能源的节点成为簇头的概率较大,因此可以均匀消耗网络能源。为了减少聚类阶段进行广播时的能源消耗和延长网络生存时间,建立了一种用于常规数据采集节点的能源消耗预测模式。仿真结果表明,相对于目前聚类的算法,该算法可实现更长传感网络生存时间、更高能源效率和卓越网络监测质量。     

多层无线异质传感网络的高效节能预测聚类算法

无线传感网络设计主要是减少能源消耗,延长网络生存时间。介绍了一种异质传感网络应用于现存聚类算法的研究,并提出了一种高效节能的预测聚类算法,此算法能适应能源和目标异质的传感网络。根据能源和通信成本等各种因素,该算法能使节点选择簇头。相对于具有较低剩余能源的节点来说,具有较高剩余能源的节点成为簇头的概率较大,因此可以均匀消耗网络能源。为了减少聚类阶段进行广播时的能源消耗和延长网络生存时间,建立了一种用于常规数据采集节点的能源消耗预测模式。相对于目前聚类的算法来说,仿真结果表明该算法可实现更长传感网络生存时间、更高能源效率和卓越网络监测质量。     

结合拓扑势与信任度调整的重叠社区发现算法

现实世界中的复杂系统可建模为复杂网络,探究复杂网络中的社区发现算法对于分析复杂网络的拓扑结构和层次结构具有重要作用。早期研究通常将网络中的节点局限在一个社区中,但随着研究的深入发现社区结构呈现重叠特性。针对现有重叠社区发现算法存在划分社区结构不稳定、忽略节点交互和属性等问题,提出一种基于网络拓扑势与信任度调整的重叠社区发现算法。融合节点的属性和结构特征计算节点的拓扑势,依据节点的拓扑势选取核心节点。从核心节点出发构建初始社区群,计算各个社区间的调整信任度,实现社区的合并与再调整,从而识别重叠社区。在多个人工模拟网络和真实网络数据集上的实验结果表明,与基于贪婪派系扩张、种子扩张等的重叠社区发现算法相比,该算法将扩展模块度最高提升至0.719,能有效识别社区结构及重叠节点,提升重叠社区检测性能。     

A Heuristic Clustering Algorithm for Mining Communities in Signed Networks

Signed network is an important kind of complex network, which includes both positive relations and negative relations. Communities of a signed network are defined as the groups of vertices, within which positive relations are dense and between which negative relations are also dense. Being able to identify communities of signed networks is helpful for analysis of such networks. Hitherto many algorithms for detecting network communities have been developed. However, most of them are designed exclusively for the networks including only positive relations and are not suitable for signed networks. So the problem of mining communities of signed networks quickly and correctly has not been solved satisfactorily. In this paper, we propose a heuristic algorithm to address this issue. Compared with major existing methods, our approach has three distinct features. First, it is very fast with a roughly linear time with respect to network size. Second, it exhibits a good clustering capability and especially can work well with complex networks without well-defined community structures. Finally, it is insensitive to its built-in parameters and requires no prior knowledge.     

一种加权稠密子图社区发现算法

目前,针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区,然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重,这些先验信息对社区发现的准确性至关重要.针对该问题,提出了基于加权稠密子图的重叠聚类算法（overlap community detection on weighted networks,简称OCDW）.首先,综合考虑网络拓扑结构及真实网络中边权重的影响,给出了一种网络中边的权重定义方法;进而给出种子节点选取方式和权重更新策略;最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较,结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.     

基于拓扑稳定性的有向网络链路预测方法

作为复杂网络研究的热门方向,有向网络链路预测旨在挖掘网络中未知的连边。网络演化机制是许多链路预测方法的理论来源和依据。现有有向相似性指标计算节点间存在连边的可能性时,忽略了实际网络演化过程中节点自身拓扑稳定性和网络结构稳定性。基于此,提出了基于拓扑稳定性的预测方法。该方法首先计算趋于稳定的节点对之间的相似度,然后计算预测节点对之间的拓扑稳定性。在三个衡量标准AUC、precision和排序分下,九个真实网络中的实验分析表明,提出方法具有较高的预测精度。     

适合复杂网络分析的最短路径近似算法

基于互联网抽取的社会网络往往具有较大的规模,这对社会网络分析算法的性能提出了更高的要求.许多网络性质的度量都依赖于最短路径信息,社会网络等现实网络往往表现出"无标度"等复杂网络特征,这些特征指示了现实网络中最短路径的分布规律.基于现实网络的拓扑特征,提出了一种适合于复杂网络的最短路径近似算法,利用通过局部中心节点的一条路径近似最短路径,该算法能够方便地用于需要最短路径信息的社会网络性质的估算,为复杂网络的近似分析提供了一种新的思路.在各种生成网络与现实网络上的实验结果表明,该算法在复杂网络上能够大幅降低计算复杂性并保持较高的近似准确性.     

Introducing a procedure for developing a novel centrality measure (Sociability Centrality) for social networks using TOPSIS method and genetic algorithm

Centrality is one of the most important fields of social network research. To date, some centrality measures based on topological features of nodes in social networks have been proposed in which the importance of nodes is investigated from a certain point of view. Such measures are one dimensional and thus not feasible for measuring sociological features of nodes. Given that the main basis of Social Network Analysis (SNA) is related to social issues and interactions, a novel procedure is hereby proposed for developing a new centrality measure, named Sociability Centrality, based on the TOPSIS method and Genetic Algorithm (GA). This new centrality is not only based on topological features of nodes, but also a representation of their psychological and sociological features that is calculable for large size networks (e.g. online social networks) and has high correlation with the nodes' social skill questionnaire scores. Finally, efficiency of the proposed procedure for developing sociability centrality was tested via implementation on the Abrar Dataset. Our results show that this centrality measure outperforms its existing counterparts in terms of representing the social skills of nodes in a social network.     

Community Detection in Complex Networks

With the rapidly growing evidence that various systems in nature and society can be modeled as complex networks, community detection in networks becomes a hot research topic in physics sociology, computer society, etc. Although this investigation of community structures has motivated many diverse algorithms, most of them are unsuitable when dealing with large networks due to their computational cost. In this paper, we present a faster algorithm ComTector which is more efficient for the community detection in large complex networks based on the nature of overlapping cliques. This algorithm does not require any priori knowledge about the number or the original division of the communities. With respect to practical applications, ComTector is challenging with five different types of networks including the classic Zachary Karate Club, Scientific Collaboration Network South Florida Free Word Association Network, Urban Traffic Network North America Power Grid and the Telecommunication Call Network. Experimental results show that our algorithm can discover meaningful communities that meet both the objective basis and our intuitions.     

语言网络研究的数学模型——从复杂网络、社会网络到语言网络

复杂网络技术的发展为大数据时代的语言研究提供了新的视角。网络方法应用到语言研究的重要目的是探索语言网络的结构特征规律和功能演化规律。该文综述了以图论为基础的复杂网络发展及社会网络、语言网络的主要数学模型,试图从复杂网络共性特征——小世界、无标度特征中进一步剥离出语言网络的个性特征,为语言符号多层级网络结构、功能研究提供参考。