基于传染病模型的LPA特征阀值社团划分方法

社团结构划分对于分析复杂网络的统计特性非常重要.在非均匀社交网络的信息传播中,社团结构划分更是一个广泛关注的研究热点,相关研究往往侧重于研究紧密连接的社团结构对于信息传播所产生的关键影响.传统社团划分方法大多基于点和边的相关特性进行构建,如标签传播算法LPA（Label Propagation Algorithm）通过半监督机器学习方法,基于网络节点标签的智能交换和社团融合过程进行社团划分,但运行效率较低.为提高LPA类算法的运行速度,使其快速收敛,并提高社团划分精度,特别是重叠社团划分精度,针对LPA算法划分中的低运行效率和低融合收敛速度,本文从标签传播的网络连接矩阵本质出发,将该矩阵的最大非零特征值与网络标签信息传播的阀值相结合,提出了新的基于传染病传播模型的社团划分方法（简称ESLPA算法,Epidemic Spreading LPA）.通过经典LFR Benchmark模拟测试网络、随机网络以及真实社交网络数据上的算法验证,结果表明该算法时间复杂度大幅优于经典LPA算法,在重叠社团划分上精确度优于基于LPA模型的经典COPRA算法,特别是在重叠社团较明显时,划分精度接近精度较高GA、N-cut和A-cut算法,明显优于GN、FastGN和CPM等经典算法.     

面向大规模网络的快速重叠社团挖掘算法

重叠社团在社交网络大数据中普遍存在.针对现有重叠社团挖掘算法易将重叠区域错误地划分为独立的社团且计算复杂的问题,提出了一种基于局部信息度量的快速重叠社团挖掘算法（Local information based Fast Overlapped Communities Detection,Li-FOCD）.首先,为节点定义局部信息度量指标——社团连接度和邻居连接度,建模节点与社团的关系,缩小了计算范围;然后,每次并行地迭代执行缩减、扩展、去重等操作,并更新局部度量指标,通过松弛每次迭代的终止条件,发现近似最优社团集合而不是最优社团,最终算法复杂度为O（m+n）.基于真实的大规模社交网络数据的试验分析表明：与当前流行的重叠社团挖掘算法相比,Li-FOCD在不损失检测质量的前提下,大幅提升了计算效率.     

机会网络中基于有权社团结构图的路由协议研究

基于社团检测的机会网络路由算法大多采用无权重网络拓扑划分社团,仅将节点间的关系抽象为一条简单的无权重的边,忽略了节点关系的强弱程度。本文通过引入权重策略改进了QCA社团更新算法,提出了一种基于有权社团结构的路由算法,该算法解决了社团关系定量化单一的问题,更能真实反映出社团成员之间的关系。算法中,节点间的交互信息转化为权重,根据不同的网络环境选择不同的权重转化方案———归一化权重（normalized weight）和非归一化权重（non-normalized weight）。路由算法在检测到周围网络环境变化时自动切换权重计算方案以适应网络环境的变化。通过在仿真环境和真实数据集上测试和分析,该算法能够将网络中的节点划分出合理的社团结构,并在保证较高的传输成功率的情况下降低网络开销。     

基于FCM的复杂网络重叠社团结构发现算法

复杂网络中的社团结构发现是对网络数据集进行数据挖掘的普遍性问题.针对网络中大量存在的重叠社团现象,提出了基于FCM的发现重叠社团结构算法,并进一步在NG模块度的基础上,给出了评价重叠社团结构的模块度函数.算法首先将网络的节点映射成欧氏空间的节点,再以此做模糊聚类得到各重叠社团结构,根据模块度函数选择最佳重叠社团结构.最后,在经典网络上的实验结果表明,算法能够得到满意度高的重叠社团结构,而且时间复杂度较低.     

基于双编码的重叠社团检测多目标优化方法

近年来,多目标进化方法已被广泛应用于重叠社团检测问题并取得了较好的社团划分性能.如何设计合适的个体编码以及进化策略是提高基于多目标进化重叠社团检测算法性能的重要因素.为此,本文设计了一种双编码表示方法对非重叠社团结构和重叠点分别进行编码,能够有效解码得到重叠社团结构.在双编码表示的基础上,本文提出了一种基于双编码的重叠社团检测多目标优化方法(DRMOEA).在DRMOEA中,为了获得好的初始个体并提高算法检测性能,本文提出了一种基于社团边界点的初始化策略.除此之外,针对双编码中的重叠点编码部分,本文提出了基于精英个体边界点的交叉策略,该策略利用社团边界信息引导种群向好的方向进化,从而有效提高了算法的检测性能.最后,在9个真实世界网络上的实验结果表明DRMOEA算法优于其他5个代表性重叠社团检测算法.     

基于多元属性的社团挖掘在意见领袖发现中的应用

意见领袖是网络舆论传播中的关键,在舆情分析中有重要意义.采用无向图建模,将链接两端节点的PageRank值与相似度,作为链接的双重属性,通过二次判别式对链接进行主次划分,将整个网络划分为核心与非核心两类用户,并将网络中的大社团进行细化,结合细化后的社团跟核心用户的划分结果找出其中相应的子社团中的意见领袖,提出了一种基于二元分类的意见领袖发现算法.     

社交网络中用户区域影响力评估算法研究

以人人网为例对在线社交网络的分析,从区域信息传播的角度出发,研究社交网络中,信息传播的微观过程.通过真实测量用户的信息传播行为,完成用户信息传播网络的构建和测量.发现区域信息传播网络中少量核心节点覆盖了大部分的网络传播行为.针对这些核心节点,文中提出了一种基于节点传播意愿和传播能力综合考察的节点传播影响力识别算法InfluenceRank,并通过与多种相关算法进行比对,验证了算法的有效性.     

基于加权内容-结构网络和随机游走的社团划分算法

针对传统模块优化社团划分算法仅能利用网络的结构信息,而无法利用同样丰富的内容信息,导致划分精度较低的问题,提出一种结合内容属性并通过给连边加权来全面优化网络拓扑结构的社团划分算法CCSRW（Classification with Content-Structure and Random Walk）.设计利用随机游走理论计算结构节点与内容节点间的相似性关系矩阵,并将结构节点映射到内容属性空间上,最终把社团划分问题转化为多维无监督聚类问题.通过在真实数据集上进行的全面实验分析,展示了相比于传统社团划分算法,本文的算法能更准确的描述网络结构,显著提高划分性能,并有效解决小社团不敏感问题,更适用于大规模复杂信息网络的社团划分.     

基于边模式的社团检测算法

为了检测网络的社团结构，提出基于统计推理的边模式社团检测方法，在计算机生成的网络中和实际网络检测了算法的可行性和准确性，并与现有的两种基于边模式的社团检测方法做了比较。实验表明，所提出的方法可以快速有效地检测出重叠社团，在性能上优于后两种方法。     

微博转发网络中的节点特征和传播模型

微博作为重要的社交网络平台,具有传播快速、平台影响大的特点.微博用户的节点特征决定了其网络影响力.研究了微博转发网络中节点的度值特征和传播模型.首先通过区分信息流动方向构建了微博转发网络;其次分别讨论了出度一入度的均值和方差,明确二者的差异,并分析了考虑节点度值特征的信息传播过程;最后通过仿真验证可以看出:边的有向性对信息传播有着显著的影响,在有向条件下,渗流阈值增加,同样概率下传播范围变小,信息传播更为困难.     

基于用户节点相似度的局部社团挖掘

随着Web2.0的迅速发展,社交网络规模变得越来越庞大,包含的信息量也越来越多。传统的从全局角度出发进行社团挖掘的算法由于较高的复杂度以及获取全网信息的困难度,不适用于大型复杂网络的社团挖掘。文中提出了一种基于节点相似度和局部中心点的社团挖掘算法,实验结果表明,该算法在保证较高准确度的同时具有线性时间复杂度。     

Research on the scalability of parallel community detection algorithms

The social network often contains a large amount of information about users and groups,such as topic evolution mode,group aggregation effect,the law of information dissemination and so on.The mining of these information has become an important task for social network analysis.As one characteristic of the social network,the group aggregation effect is characterized by the community structure of the social network.The discovery of community structure has become the basis and key point of other social network analysis tasks.With the rapid growth of the number of online social network users,the traditional community detection methods have been difficult to be used,which contributes to the development of parallel community detection technology.The current mainstream parallel community detection methods,including Louvain algorithm and label propagation algorithm,were tested in the large-scale data sets,and corresponding advantages and disadvantages were pointed out so as to provide useful information for later applications.     

一种基于边界节点识别的复杂网络局部社区发现算法

在网络日益巨大化和复杂化的背景下,挖掘全局网络的社区结构代价较高。因此,基于给定节点的局部社区发现对研究复杂网络社区结构有重要的应用意义。现有算法往往存在着稳定性和准确性不高,预设定阈值难以获取等问题。该文提出一种基于边界节点识别的复杂网络局部社区发现算法,全面比较待合并节点的连接相似性进行节点聚类;并通过边界节点识别控制局部社区的规模和范围,从而获取给定节点所属社区的完整信息。在计算机生成网络和真实网络上的实验和分析证明,该算法能够自主挖掘给定节点所属的局部社区结构,有效地提升局部社区发现稳定性和准确率。     

融合标签平均划分距离和结构关系的微博用户可重叠社区发现

提出了一种融合标签平均划分距离和结构关系的微博用户可重叠社区发现算法.首先从信息论与距离的概念出发,定义基于核心标签平均划分距离的准划分算法;再根据用户关注关系定义结构属性向量,并计算用户结构相异度,进而对核心标签平均划分距离和用户结构相异度进行权重调节,得到综合划分相异度;最后将综合划分相异度最低的标签所划分出的分组作为本次循环的新社区;实验表明,该方法能够识别可重叠社区且具有实际应用意义.     

Analysing social behaviour and message dissemination in human based delay tolerant network

Recent advances in mobile communication shows proliferation in networks formed by human carried devices known as the pocket switched network (PSN). Human beings are social animals. They tend to form groups and communities, and have repetitive mobility pattern which can be used to disseminate information in PSNs. In this paper, we give a deeper insight to the nature of community formation and how such information can be used to help opportunistic forwarding in mobile opportunistic networks. Using real world mobility traces, we first derive the adjacency list for each node and form the contact graph. Using tools from social network analysis we then determine various node properties like centrality and clustering coefficient and graph properties like average path length and modularity. Based on the derived graph properties, node encounter process and nature of message dissemination in PSNs, we propose two social based routing, known as the contact based routing and community aware two-hop routing. We compare the proposed routing techniques with generic epidemic and prophet routing and Bubble-Rap, a social based routing. Results show that the proposed algorithms is able to achieve better delivery ratio and lower delay than Bubble Rap, while reducing the high overhead ratio of epidemic and prophet routing.     

基于Attention深度随机森林的社区演化事件预测

在网络结构不断变化的同时,社区结构也随之演化.社区结构在不同时间片的变化可定义为四种不同的演化事件：持续、分离、融合和消失.本文运用网络表示学习的方法,对网络进行图嵌入编码映射到低维向量空间中,研究动态社区演化事件的预测.特征方面,在传统的社区内部属性特征、时间片间属性特性变化和前段时间片的社区演化事件的特征维度的基础上,引入潜在结构特征表征四种演化事件,运用随机游走和Softmax思想获取潜在的结构特征;模型方面,引入深度随机森林的策略,同时采用attention机制、蒙特卡洛特征采样策略进行特征融合和特征训练,克服了已有算法仅获取局部结构特征的缺陷.实验在DBLP、FACEBOOK和Bitcoin数据集上,对比SVM、XGBOOST和RIDGE模型训练,证实了新提出的算法模型对最终预测准确率有很大的提升.     

一种关注消息时效性的机会社会网络中节点传播能力分析模型

当前评估节点传播能力的工作大多针对静态网络.本文采用演化图模型对机会社会网络进行刻画,通过将传统通路(walk)的概念和静态图中的Katz中心性度量扩展到动态网络中,提出了一种基于历史相遇记录评估节点消息分发能力的方法.进一步,针对消息的时效性特性,本文提出了消息随时间推移效用递减的节点传播能力分析模型,该模型考虑了消息所有可能经历的空间和时间通路,并沿时间方向向下加权以描述消息时效性递减效应,可用于有效计算和预测节点的消息转发能力.本文的结论通过真实数据得到了验证.     

融合节点分析与边分析的复杂网络社区识别算法

针对边社区识别与节点型社区识别两类算法在识别社区过程中均存在相应缺陷,影响复杂网络社区识别质量的问题,提出融合节点分析与边分析的复杂网络社区识别（CDHNE）算法。该算法首先运用边在网络中较为稳定的特点,在算法执行初期通过边社区识别构建较为准确的社区结构;然后利用节点较为灵活的特点,在边社区形成后,对边社区的边缘进行精确识别,更准确地识别出复杂网络中的社区结构。在计算机生成网络实验中,当网络的社区结构逐渐变得模糊、重叠节点数量与重叠节点归属社区数量不断增加时,CDHNE算法的社区识别精度较传统算法平均提高10%,在重叠节点识别精度上较传统算法平均提高15%;在真实网络实验中,算法识别的社区结构紧密度较好,特别是面对拥有十几万个节点的大规模网络时,CDHNE算法高质量地完成了识别任务,EQ值达到0.412 1。实验结果表明,CDHNE算法在运行稳定性和处理大规模网络方面具有优势。