基于非负矩阵分解的用户话题兴趣度算法

Web媒体被公认为继报纸、广播、电视之后的“第四媒体”.而Web2.0的迅速普及,又使当今的Web媒体呈现了一种“自媒体”形式,即每个用户既是信息的接受者,也是信息发布者和信息转发者,在信息传递过程中,用户与用户互动,影响信息传播的进程.用户本身的特性对于传播有很大影响,信息传播依赖于用户个体的行为模式.因此,需要对用户和传播话题之间的关系进行建模,来度量用户对某个话题的感兴趣程度.论文提出了有效的算法来对用户进行感兴趣的话题推荐,该算法基于非负矩阵分解理论,分析用户发表过的内容,将用户感兴趣的话题推荐给该用户.该文针对研究小组下载的真实数据集-科学网数据集进行实验分析,实验结果表明算法能够有效地将用户感兴趣的话题推荐给用户.     

基于黎曼流形的多视角谱聚类算法

现有的多视角谱聚类算法大多只线性结合了各视角的基拉普拉斯矩阵,未考虑不同视角数据的差异性对最优拉普拉斯矩阵的影响,存在聚类性能受限的问题。提出一种基于黎曼几何均值与高阶拉普拉斯矩阵的谱聚类算法(RMMSC),挖掘多视角数据中的高阶连接信息与流形信息,提高最优拉普拉斯矩阵对各视角的信息利用率。按一定的权重线性结合数据单一视角的各阶拉普拉斯矩阵,得到每个视角的基拉普拉斯矩阵,通过低阶与高阶连接信息的结合使用,充分体现多视角数据集的全局结构。在此基础上,计算各视角基拉普拉斯矩阵的黎曼几何均值,将其作为最优拉普拉斯矩阵输入谱聚类算法,得到聚类结果。相比于传统矩阵算数均值的计算,基于黎曼流形的黎曼几何均值能够更好地恢复互补层数据的流形信息。实验结果表明,RMMSC在多组标准数据集上聚类效果优于ONMSC、MLAN、AMGL等算法。其中,在Flower17数据集上,精确度较基准算法ONMSC提高了2.14%,纯度提高了1.7%,且收敛性较好。     

基于矩阵分解的属性网络嵌入和社区发现算法

属性网络不但包含节点之间复杂的拓扑结构,还包含拥有丰富属性信息的节点,其可以比传统网络更有效地建模现代信息系统,属性网络的社区划分对于分析复杂系统的层次结构、控制信息在网络中的传播和预测网络用户的群体行为等方面具有重要的研究价值.为了更好地利用拓扑结构信息和属性信息进行社区发现,提出了一种基于矩阵分解的属性网络嵌入和社区发现算法(CDEMF).首先提出基于矩阵分解的属性网络嵌入方法,基于网络局部链接信息计算相邻节点的相似性,将其与属性接近度联合建模,通过矩阵分解的分布式算法得到每个节点对应的低维嵌入向量,即把网络节点映射为低维向量表示的数据点集合.接着提出基于曲率和模块度的社区划分方法,自动确定数据点集合中蕴含的社区数量,并通过对数据点集合聚类完成属性网络社区划分.在真实网络数据集上,将CDEMF方法与其他8种知名算法进行比较,实验结果表明CDEMF具有良好的性能.     

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

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

一种保留社区结构信息的网络嵌入算法

现有网络嵌入算法大多只保留网络的微观结构信息,忽略了网络中普遍存在的社区结构信息。为提高网络表示质量,提出一种保留社区结构信息的网络嵌入算法PCNE。通过最大化节点之间的一阶和二阶相似性,对网络的微观结构进行建模,同时通过分解可反映网络社区结构信息的社区结构嵌入矩阵,对网络的社区结构信息进行建模。将构建的2个模型融合到统一的联合非负矩阵分解框架中,结合相似度矩阵和社区隶属度矩阵得到融合社区结构信息的节点表示向量。在5个真实公开数据集上进行节点分类实验,结果表明,与DeepWalk、Node2vec、LINE算法相比,PCNE可使Micro-F1值提升0.96%~13.1%,验证了算法的有效性。     

动态加权网络中的演化社区发现算法研究

在动态网络中发现社区结构是一个非常复杂而有意义的过程,可以更好地观察和分析网络的演化情况。针对动态加权网络中的社区发现问题,提出了一种结合历史网络社区结构的算法,叫做动态加权网络中的演化社区发现算法（ECDA）。该算法分为两步：结合历史社区和网络结构信息,计算当前时间跳的输入矩阵;然后通过该输入矩阵计算得到结合历史时间跳信息的社区划分结果。该算法有以下优点：可以自动发现动态加权网络中每个时间跳的社区结构;对网络结构的变化和社区结构的变化具有较高的敏锐性。在人工数据集和真实数据集中进行了实验,实验结果证明该算法可以有效地发现动态加权网络中的社区结构,与其他算法相比具有较好的竞争力。     

基于联合矩阵分解的动态异质网络社区发现方法

动态网络的社区发现是目前复杂网络分析领域的重要研究内容,然而现有动态网络社区发现方法主要针对同质网络,当网络包含多种异质信息时,现有方法不再适用。针对这个问题,本文提出了一个基于联合矩阵分解的动态异质网络社区发现方法,首先计算动态异质网路中各个快照图的拓扑相似度矩阵和多关系相似度矩阵,其次利用时序联合非负矩阵分解方法,约束各个时刻快照图的社区划分,最后在真实网络数据集上的实验结果表明,该算法可以有效检测出动态异质网络中潜在的社区结构。     

基于小波去噪的有向加权社团发现研究

目前大部分社团发现方法都是针对无向无权图,但实际的社会媒体中的社团内部个体交互过程可以抽象为一个有向加权图,并且权重中含有大量的噪声.为解决有向加权社团的划分问题,本文提出一种基于非负矩阵分解(Nonnegative matrix factorization,NMF)可去噪声的社团发现方法.该方法通过小波阈值去噪对社会网络数据进行去噪处理,结合有向加权的非负矩阵分解算法对去噪后的数据集进行社团发现,准确找出社团结构.在社会媒体的实验数据集和标准数据集上的实验结果表明,该算法针对带噪声的有向加权图社团发现问题具有良好划分性能,SNR为15时,在Lesmis数据集上的社团划分准确率达到96％,划分模块度值提高了29％.本文为解决带噪的有向加权的社会网络数据提供了切实有效的处理方法.     

融合先验信息的非负矩阵分解社区发现算法*

针对复杂网络社区发现问题,为了获得更准确、可解释性的社区划分结果,提出融合先验信息的半监督非负矩阵分解算法,给出优化目标的求解方法.文中算法利用先验信息直接约束社区指示矩阵,构造优化目标函数,获得更有意义的社区划分结果.真实数据集上的实验表明该算法的有效性,减小先验信息的融入对利用非负矩阵分解进行节点重要性等属性分析工作带来的不利影响,并且适用于加权和非加权等不同的网络.     

一种融合多维信息的移动社区发现方法

为解决传统社区发现算法难适用于大型复杂异质的移动网络的问题,利用移动网络使用详单数据（Usage Detail Record, UDR）和移动用户社交数据构建网络模型,提出一种融合多维信息的移动社区发现方法BNMF-NF。该方法综合考虑用户社交关系和时空行为,给出用户社交相似度、位置分布相似度和主题偏好相似度,利用加权网络融合方法融合多维相似关系构建用户相似网络,并运用有界非负矩阵分解技术实现社区结构的检测。在Foursquare和电信数据集上的实验结果表明,BNMF-NF方法能够有效发现移动网络中用户社区结构。     

Dual modularity optimization for detecting overlapping communities in bipartite networks

Many algorithms have been designed to discover community structure in networks. These algorithms are mostly dedicated to detecting disjoint communities. Very few of them are intended to discover overlapping communities, particularly the bipartite networks have hardly been explored for the detection of such communities. In this paper, we describe a new approach which consists in forming overlapping mixed communities in a bipartite network based on dual optimization of modularity. To this end, we propose two algorithms. The first one is an evolutionary algorithm dedicated for global optimization of the Newman’s modularity on the line graph. This algorithm has been tested on well-known real benchmark networks and compared with several other existing methods of community detection in networks. The second one is an algorithm that locally optimizes the graph Mancoridis modularity, and we have adapted to a bipartite graph. Specifically, this second algorithm is applied to the decomposition of vertices, resulting from the evolutionary process, and also characterizes the overlapping communities taking into account their semantic aspect. Our approach requires a priori no knowledge on the number of communities searched in the network. We show its interest on two datasets, namely, a group of synthetic networks and real-world network whose structure is also difficult to understand.     

一种联合拓扑与属性的社区模糊划分算法

现有的社区发现算法通常基于结构特性进行社区划分,对节点属性特征欠缺考虑。为此,提出一种基于模糊等价关系的社区发现算法。用完全相异距离指数的概念将拓扑结构与属性特征相结合,以此作为隶属关系建立模糊等价关系矩阵,选择合适的聚类f阂值对网络进行社区划分。实验结果证明,与传统的GN算法相比,该算法发现社区的准确率较高,在相同社区内的节点连接紧密且具有同质性。     

基于SimRank全局矩阵平滑收敛的网络社区发现

SimRank方法是一种基于图的拓扑结构信息来衡量任意两个对象间相似程度的方法,针对在真实的大规模社交网络中节点与节点之间的迭代计算过程需要消耗大量的时间,提出了一种基于SimRank全局矩阵平滑收敛的网络社区发现方法（SimRank global smooth convergence,SGSC）。首先,该算法通过经典度量来识别网络中的初始核心节点;然后利用矩阵平滑收敛来计算SimRank得到最终核心节点;最后,基于全局收敛矩阵,将社区聚集在核心节点周围,使用Closeness指数合并两个社区,通过递归的重复该过程,聚类出最终社区。在3种真实的不同规模的社交网络中将SGSC和其他2种具有代表性的方法进行比较,并验证了提出的算法在不同规模的社交网络中社区划分的准确率和算法运行的时间性能上有所提升。     

网络社区发现的多目标分解粒子群优化算法

通过分析社会网络中社区发现问题的优化目标,构造了社区发现的多目标优化模型,提出一种网络社区发现的多目标分解粒子群优化算法。该算法采用切比雪夫法将多目标优化问题分解为多个单目标优化子问题,使用粒子群优化(PSO)算法对社区结构进行挖掘,并引入了一种新颖的基于局部搜索的变异策略以提高算法的搜索效率和收敛速度,该算法克服了单目标优化算法存在的解单一以及难以发现社区层次结构的缺陷。人工网络及真实网络上的实验结果表明,该算法能够快速准确地挖掘网络社区并揭示社区的层次结构。     

一种基于增广网络的快速微博社区检测算法

微博是当前最流行的在线社交媒体之一,有效地检测出微博用户的社区结构,能够帮助人们理解微博社交网络的结构和用户的行为特征,从而为用户提供个性化的服务。然而,现有社区检测算法大多只考虑社交网络节点之间的直接链接关系,忽略节点自身的内容特征。针对此问题,提出一种基于增广网络的快速微博社区检测算法。该算法通过融合社交网络的链接信息以及用户在微博上所发布的博文内容信息构建增广网络,然后以模块度为目标函数快速挖掘增广网络中的主题社区。通过真实微博社交网络的实验表明,提出的算法能够高效地检测出社交网络的主题社区。
     

Community detection in multiplex networks via consensus matrix

In complex network of real world,there are many types of relationships between individuals,and the more effective research ways for this kind of network is to abstract these relationship as a multiplex network.More and more researchers are attracted to be engaged in multiplex network research.A novel framework of community detection of multiplex network based on consensus matrix was presented.Firstly,this framework merges the structure of multiplex network and the information of link between each node into monoplex network.Then,the community structure information of each layer network was obtained through consensus matrix,and the traditional community division algorithm was utilized to carry out community detection of combine networks.The experimental results show that the proposed algorithm can get better performance of community partition in the real network datasets.