基于节点中心性和社区相似性的快速标签传播算法

为了减少标签传播算法(LPA)中不必要的更新、解决算法准确率低且稳定性差的问题,提出了基于节点中心性和社区相似性的快速标签传播算法(FNCS_LPA)。按照节点中心性度量对网络的节点从低到高进行排序后加入节点信息列表,利用节点信息列表来指导更新过程,提高社区发现的稳定性并避免不必要的更新;采取基于社区相似性的更新规则,提高了社区发现的准确率。在真实社会网络和LFR基准网络上进行实验:相比LPA和三种较好的LPA改进算法,FNCS_LPA在执行速度方面提升了几十倍,真实社会网络的模块度也相对较高,在社区结构比较模糊的LFR基准网络上的归一化互信息有明显的优势。实验结果表明FNCS_LPA在提高执行速度的基础上,提高了算法的稳定性和准确率。

基于马尔可夫相似性增强和网络嵌入的社区发现

社区结构普遍存在于自然界的各种复杂网络中,是网络结构的重要特征之一。社区发现算法可以识别网络中的有用信息,有助于分析网络的结构和功能,被广泛应用于社交网络、生物和医学等领域。文中针对目前基于局部相似性的复杂网络社区发现算法精确度不高的问题,提出了一种基于马尔可夫相似性增强和网络嵌入的社区发现算法。首先,受马尔可夫链思想启发,提出了一种马尔可夫相似性增强方法,通过对初始网络的马尔可夫迭代状态进行转移,来获取稳态的马尔可夫相似性增强矩阵,根据马尔可夫相似性指标对网络进行初始的社区划分。然后结合网络的拓扑结构和网络嵌入,提出了一种新的社区相似性指标,将初始社区结构中的小社区与其连接紧密的社区合并,得到网络社区结构。在7个真实网络和可变参数的人工网络上,通过与其他5个知名社区发现算法的比较,证明了所提算法具有良好的社区发现效果。

基于结构相似度的多尺度局部社区发现算法

社会网络规模巨大且结构动态变化给传统社区发现算法带来了巨大挑战,局部社区算法通过种子节点进行扩展得到局部社区,较好解决了这些问题。结合节点结构相似度在传统社区定义的基础上提出了一种新的社区定义,在该定义基础上引入尺度因子并定义了结构模块度,基于该模块度提出了一种多尺度局部社区发现算法,并改进该算法使之应用到局部重叠社区发现。通过实验选择效果较好的节点结构相似度,在真实网络中和其他局部社区发现算法进行对比实验,结果表明该算法具有较好的性能。

基于边图的线性流重叠社区发现算法

重叠网络的社区发现是复杂网络研究中的重要问题。为了提高网络中重叠社区发现的时间效率,提出一种基于边图的线性流重叠社区发现算法LBSA。算法首先对于边图网络中的边进行随机的依次处理,完成节点的初步社区划分,再将其中重叠小社区合并到相似度最大的其他大社区中得到最终的社区。通过以上步骤,算法能够以接近线性的时间复杂度得到网络的重叠结构。从最终的实验结果来看,与其他算法相比,该算法能够在更短的时间有质量地发现网络中的重叠社区。

针对有向图的局部扩展的重叠社区发现算法

当前社区发现算法主要是针对无向图研究社区结构,但在实际复杂网络中,链接关系时常表现出非对称性或方向性,比如Twitter的用户关注关系,文献网络的引用关系,网页之间的超链接关系等应用网络。因此,本文依据信息在复杂网络中的传播规律和流动方向性,提出了k-Path共社区邻近相似性概念及计算方法,用于衡量结点在同一社区的相似性程度,并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法(Local and wave-like extension algorithm of detecting overlapping community,LWS-OCD)。在真实数据集上的实验表明,共社区邻近相似性概念实现了有向到无向的合理转换,而且提高了社区结点的聚集效果,LWSOCD算法能够有效地发现带权无向图中的重叠社区。

有向复杂网络软件异常交互执行行为挖掘算法

挖掘软件异常交互行为直接影响软件的安全性,研究有向复杂网络软件异常交互执行行为挖掘算法,精准挖掘存在异常交互执行行为的关键节点。以社交网络形式描绘有向复杂网络,分割社交网络图获取数个社区,利用局部哈希法提取社区特征值即社区内节点与边的质量分数,通过局部散列结合质量分数得到社区相似度,对比分析相似度与异常交互执行行为阈值,确定存在异常交互执行行为的社区即异常区域;利用局部中心性算法挖掘确定区域内异常交互执行行为的关键函数节点,其中按照函数节点积累缺陷能力挖掘关键调动函数节点,按照传播缺陷能力挖掘关键被调函数节点。仿真结果表明,上述算法可有效确定网络软件存在异常交互执行行为的区域;有向边权重为0.4时,上述算法的挖掘效果最佳;在不同软件调用次数时,上述算法可精准挖掘异常交互执行行为的关键函数节点。

SERVICE COMMUNITY CONSTRUCTION METHOD OF INTERNET OF THINGS BASED ON SEMANTIC SIMILARITY

Internet of Things (IoT) as an important and ubiquitous service paradigm is one of the most important issues in IoT applications to provide terminal users with effective and efficient services based on service community. This paper presents a semantic-based similarity algorithm to build the IoT service community. Firstly, the algorithm reflects that the nodes of IoT contain a wealth of semantic information and makes them to build into the concept tree. Then tap the similarity of the semantic information based on the concept tree. Finally, we achieve the optimization of the service community through greedy algorithm and control the size of the service community by adjusting the threshold. Simulation results show the effectiveness and feasibility of this algorithm.

基于重要结点的社区发现算法

复杂网络中内部的社区结构是复杂网络结构特征和属性特征的具体体现。首先依据模块度最大化理论计算网络的模块度矩阵的最大k特征向量矩阵;然后提出聚类中心方法,并用于求出k个社团的重要结点作为k聚类中心,利用欧几里得距离计算每一个结点到k个聚类中心的距离,将结点分配到距离聚类中心最近的社区中;最后对网络应用k-means方法进行迭代计算,得到k个社区的划分。分别在Karate Club Network和American College Football数据集上对算法进行了实验验证,实验结果表明该算法可以有效发现潜在社区,其纯度与模块度比已有的社区发现算法都有一定的提高,并且迭代次数较少,效率较高。