复杂条件下的社区搜索方法

社区搜索旨在寻找包含给定节点集的社区，能够快速获取个性化的社区信息.针对现有社区搜索算法难以满足复杂搜索条件的现状，提出条件社区搜索这一新问题.解决该问题有助于对社交网络进行智能分析，在复杂搜索条件下为用户提供更好的社区结果.首先，基于布尔表达式，给出条件社区搜索问题的形式化定义，可有效表达给定节点不能出现在社区内以及给定节点中至少有一个出现在社区内的要求.接着，提出解决条件社区搜索问题的通用框架，包括对搜索条件进行简化、根据简化后的搜索条件进行多次单项条件社区搜索、合并各单项条件社区搜索的结果等主要步骤.同时，提出"社区搜索+过滤"的方法和给点加权的方法来进行单项条件社区搜索.最后，真实数据集上的大量实验结果表明所提方法的正确性和有效性.     

复杂属性条件下基于Spark的clique社区搜索算法

现有的社区搜索算法难以在网络中找到满足给定复杂属性条件的社区。同时,随着网络规模的不断扩大,单机串行的社区搜索算法也已无法有效地处理大规模的网络数据。针对复杂属性条件下的clique社区搜索问题,提出一种基于Spark的搜索算法。在Spark并行计算框架的基础上,结合图的结构特征和内容属性,根据由布尔表达式定义的复杂属性条件采取不同的搜索策略,搜索时利用属性的搜索成本和扩展成本进行局部优化,从而加快搜索过程。实验结果表明,与结构优先或属性优先的社区搜索算法相比,该算法在不同属性条件、网络规模和节点数目的情况下均能保证搜索准确性并提高搜索效率。     

基于位置社交网络的用户社区和属性位置簇搜索

针对当前社区搜索问题不能完全满足用户活动位置推荐的需求，提出了属性地理社会社区搜索问题(AGCS)。该问题是从带有属性的基于位置的社交网络中寻找紧密连接的用户社区和属性位置簇的工作。定义一个基于属性约束和签到信息的新社区度量用于衡量结果质量，并提出三种新的搜索算法来解决该问题：一种基本算法、一种基于贪心扩展策略的局部算法以及优化的局部算法。实验证明提出的算法能够在带有属性的基于位置的社交网络中有效地搜索高质量的用户社区和属性位置簇，局部算法社区分数较基本算法增加近1.5倍，优化的局部算法在保证社区质量的基础上将算法效率提升到原来的近40倍。     

面向二分网络的谱近似社区搜索方法

社区搜索旨在从网络中查找给定查询节点所在的局部社区，基于谱的社区搜索方法是流行的方法之一。现有基于谱的社区搜索方法多面向简单网络而无法处理具有2类实体关联的二分网络，且面向二分网络的社区挖掘方法多是对网络进行整体划分。据此，提出了面向二分网络的谱近似社区搜索方法，旨在将谱方法引入到二分网络中进而精确定位与查询节点关联紧密的社区。具体来说，首先考虑二分网络中2类实体的关联，基于局部模块度设计了面向二分网络的局部模块度；其次，基于谱图理论，在二分网络上利用融合不同实体关联的模块度矩阵局部逼近特征子空间，设计了适用于二分网络的谱方法；最后，利用结合谱性质的二分网络上的局部模块度，设计了谱子空间中以查询节点集为支撑的稀疏指示向量的线性规划问题，目标社区可通过线性规划问题的求解而获得。真实数据集上的实验结果表明了本文方法有效性和效率。     

基于邻域k-核的社区模型与查询算法

现实生活中的网络通常存在社区结构,社区查询是图数据挖掘的基本任务.现有研究工作提出了多种模型来识别网络中的社区,如基于k-核的模型和基于k-truss的模型.然而,这些模型通常只限制社区内节点或边的邻居数量,忽略了邻居之间的关系,即节点的邻域结构,从而导致社区内节点的局部稠密性较低.针对这一问题,本文将节点的邻域结构信息融入k-核稠密子图中,提出一种新的基于邻域连通k-核的社区模型,并定义了社区的稠密度.基于这一新模型,研究了最稠密单社区搜索问题,即返回包含查询节点集且具有最高稠密度的社区.在现实生活图数据中,一组查询节点可能会分布在多个不相交的社区中.为此,本文进一步研究了基于稠密度阈值的多社区搜索问题,即返回包含查询节点集的多个社区,且每个社区的稠密度不低于用户指定的阈值.针对最稠密单社区搜索和基于稠密度阈值的多社区搜索问题,首先定义了边稠密度的概念,并提出了基于边稠密度的基线算法.为了提高搜索效率,设计了索引树和改进索引树结构,能够支持在多项式时间内返回查询结果.通过与基线算法在多组数据集上的对比,验证了基于邻域连通k-核的社区模型的有效性和所提出查询算法的效率.     

异质信息网络的复杂条件社区搜索

社区是信息网络的重要属性, 社区搜索旨在寻找满足用户给定条件的节点集合, 是信息网络分析的重要研究内容. 异质信息网络由于包含更加全面、丰富的结构和语义信息, 所以异质信息网络的社区搜索近年来受到人们的广泛关注. 针对现有异质信息网络的社区搜索方法难以满足复杂条件社区搜索要求的不足, 定义了复杂条件社区搜索问题, 提出了考虑非对称元路径、受限元路径和禁止节点约束的搜索算法. 3种算法分别通过元路径补全策略、调整带标签的批量搜索策略和拆分复杂搜索条件的方式搜索社区, 同时针对禁止节点约束的搜索算法设计了基于剪枝策略和近似策略的优化算法以提高搜索效率. 在真实数据集上进行了大量实验, 实验结果证明了所提算法的有效性和高效性.     

基于motif连通性的社区搜索方法

社区搜索的目标是从数据图中得到包含查询顶点的紧密子图,在社会学、生物学等领域有着广泛应用。针对现有基于子图连通性的社区模型的基础连通结构都是完全连通图,无法满足实际应用中用户对社区结构多样性的需求的问题,提出一种基于motif连通性的社区搜索方法,其中包括基于motif连通性的社区（MCC）模型以及两个相应的社区搜索算法——MPCS(Motif-Processed Community Search)算法和基于MP-index的社区搜索算法。MCC模型可以协助用户自由指定社区的基础连通结构,MPCS算法可以用来解决MCC的搜索问题。此外,提出两个分别针对motif实例搜索过程及所属社区判断过程的剪枝优化技术。最后,设计了MP-index以避免社区搜索过程中的冗余遍历操作。在多个真实数据集上进行实验的结果表明：剪枝优化可以使MPCS算法的耗时减少60%～85%,而基于MP-index的社区搜索算法相较于加入剪枝优化的MPCS算法,效率提升普遍达到了2～3个数量级。可见,所提方法在商品推荐和社交网络等问题上有着实际应用价值。     

异质网络中基于关键词属性的Truss社区搜索

社区搜索旨在信息网络中寻找与用户指定的查询节点高度相关的稠密连通子图,是社会网络分析的重要研究内容。现有的社区搜索方法大多是针对同质网络,但现实中的信息网络通常是包含多种节点类型和多种关系类型的属性异质网络。提出了异质网络中基于元路径P和元结构S的P-距离和S-距离及(k,d,P)-truss和(k,d,S)-truss社区模型以度量子图的结构内聚性,同时提出了关键词属性得分函数用于度量不同子图的关键词属性相关性,最后提出了搜索具有最高关键词属性得分的(k,d,P)-truss和(k,d,S)-truss的社区搜索算法。搜索算法能够找到同时具有结构内聚性和关键词属性相关性的个性化社区,并且支持限制查询节点与社区内任意节点的最大距离d来控制社区搜索的范围。在真实数据集上与相关的社区搜索算法进行了实验对比,结果证明了所提算法的有效性和可行性。     

局部搜索与遗传算法结合的大规模复杂网络社区探测

基于遗传算法的复杂网络社区探测是当前的研究热点. 针对该问题,本文在分析网络模块性函数Q的局部单调性的基础上, 给出一种快速、有效的局部搜索变异策略, 同时为兼顾初始种群的精度和多样性以达到进一步提高搜索效率的目的, 采用了标签传播作为初始种群的产生方法;综上,提出了一个结合局部搜索的遗传算法(Genetic algorithm with local search, LGA). 在基准网络及大规模复杂网络上对LGA进行测试, 并与当前具有代表性的社区探测算法进行比较, 实验结果表明了文中算法的有效性与高效性.     

基于结构稳定性校准的在线式社区识别

本文探讨在线社会网络的社区识别问题, 重点研究网络演变特性对社区结构产生的影响. 首先基于节点的邻域倾向性提出社区稳定性的概念并给出稳定社区的快速识别算法, 然后设计了一种基于事件的社区稳定性校准算法以此识别新网络的社区结构. 由于算法的局部搜索策略, 该方法无需在新时间片段重复执行, 并且可以在无参数条件下识别加权网络中具有任意形状的社区结构. 在人工合成网络和真实网络上的实验结果验证了算法的可行性和有效性.     

Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm

Community structure is one of the most important properties in social networks,and community detection has received an enormous amount of attention in recent years.In dynamic networks,the communities may evolve over time so that pose more challenging tasks than in static ones.Community detection in dynamic networks is a problem which can naturally be formulated with two contradictory objectives and consequently be solved by multiobjective optimization algorithms.In this paper,a novel multiobjective immune algorithm is proposed to solve the community detection problem in dynamic networks.It employs the framework of nondominated neighbor immune algorithm to simultaneously optimize the modularity and normalized mutual information,which quantitatively measure the quality of the community partitions and temporal cost,respectively.The problem-specific knowledge is incorporated in genetic operators and local search to improve the effectiveness and efficiency of our method.Experimental studies based on four synthetic datasets and two real-world social networks demonstrate that our algorithm can not only find community structure and capture community evolution more accurately but also be more steadily than the state-of-the-art algorithms.     

一种基于随机块模型的快速广义社区发现算法

随机块模型可以生成各种不同结构(称作广义社区,包括传统社区、二分结构、层次结构等)的网络,也可以根据概率对等原则发现网络中的广义社区.但简单的随机块模型在网络生成过程建模和模型学习方面存在许多问题,导致不能很好地发现实际网络的结构,其扩展模型GSB(general stochastic block)基于链接社区思想发现广义社区,但时间复杂度限制其在中大型规模网络中的应用.为了在无任何先验的情形下探索不同规模网络的潜在结构,基于GSB 模型设计一种快速算法FGSB,更快地发现网络的广义社区.FGSB 在迭代过程中动态学习网络结构参数,将GSB 模型的参数重新组织,减少不必要的参数,降低算法的存储空间;对收敛节点和边的参数进行裁剪,减少每次迭代的相关计算,节省算法的运行时间.FGSB 与GSB 模型求解算法有相同的结构发现能力,但FGSB 耗费的存储空间和运行时间比GSB 模型求解算法要低.在不同规模的人工网络和实际网络上验证得出:在近似相同的准确率下,FGSB 比GSB 模型求解算法快,且可发现大型网络的广义社区.     

基于LDA的结构-内容联合社团发现模型

在社会网络中,根据已有的连接关系和文本信息发掘社会网络中的社团不但可以将相似的用户划分在一个社团,还可以用来预测网络中潜在的连接关系。为了提高社会网络中社团发现的性能,本文提出了一种基于LDA的结构-内容联合社团发现模型。首先,对社会网络的图论描述进行转化,使其适用于LDA模型。其次,对LDA模型描述进行扩充,使其包含了用户间交互的文本信息。最后,通过Gibbs采样方法对模型的参数进行估计。实验表明,本文提出的社团发现模型与其它相关方法相比较,社团发现得到的社团不仅用户间连接的紧密度和用户共享兴趣爱好的强度高,而且可以更好地用于社会网络中潜在连接的预测。     

基于自适应Memetic算法的多目标复杂网络社区检测

针对提高复杂网络社区检测准确度问题, 提出了一种自适应Memetic算法的多目标社区检测算法。在全局搜索中利用Logistic函数来设置与全局优化相应的交叉概率和变异概率,并将多目标优化问题转化成同时最小优化Kernel K-Means和Ratio Cut这两个目标函数;在局部搜索中利用权重将两个目标函数合并成一个局部优化目标,并采用爬山搜索来寻找个体最优。在虚拟和真实网络实验平台下,与五个基于遗传算法的方法以及Fast Modularity算法相比,结果表明算法能有效提高社区检测准确度,具有更好的寻优效果。     

Force-Based Incremental Algorithm for Mining Community Structure in Dynamic Network

Community structure is an important property of network. Being able to identify communities can provide invaluable help in exploiting and understanding both social and non-social networks. Several algorithms have been developed up till now. However, all these algorithms can work well only with small or moderate networks with vertexes of order 104. Besides, all the existing algorithms are off-line and cannot work well with highly dynamic networks such as web, in which web pages are updated frequently. When an already clustered network is updated, the entire network including original and incremental parts has to be recalculated, even though only slight changes are involved. To address this problem, an incremental algorithm is proposed, which allows for mining community structure in large-scale and dynamic networks. Based on the community structure detected previously, the algorithm takes little time to reclassify the entire network including both the original and incremental parts. Furthermore, the algorithm is faster than most of the existing algorithms such as Girvan and Newman＇s algorithm and its improved versions. Also, the algorithm can help to visualize these community structures in network and provide a new approach to research on the evolving process of dynamic networks.     

COMPARISON AND SELECTION OF OBJECTIVE FUNCTIONS IN MULTIOBJECTIVE COMMUNITY DETECTION

Detecting communities of complex networks has been an effective way to identify substructures that could correspond to important functions. Conventional approaches usually consider community detection as a single‐objective optimization problem, which may confine the solution to a particular community structure property. Recently, a new community detection paradigm is emerging: multiobjective optimization for community detection, which means simultaneously optimizing multiple criteria and obtaining a set of community partitions. The new paradigm has shown its advantages. However, an important issue is still open: what type of objectives should be optimized to improve the performance of multiobjective community detection? To exploit this issue, we first proposed a general multiobjective community detection solution (called NSGA‐Net) and then analyzed the structural characteristics of communities identified by a variety of objective functions that have been used or can potentially be used for community detection. After that, we exploited correlation relations (i.e., positively correlated, independent, or negatively correlated) between any two objective functions. Extensive experiments on both artificial and real networks demonstrate that NSGA‐Net optimizing over a pair of negatively correlated objectives usually leads to better performances compared with the single‐objective algorithm optimizing over either of the original objectives, or even to other well‐established community detection approaches.     

基于权重信息挖掘社会网络中的隐含社团

社团结构是一种普遍存在于各类真实网络中的结构特性.挖掘网络的社团结构对于理解网络的功能与行为有着重要作用.然而,现有的各种社团挖掘算法仅仅基于网络拓扑结构信息,而忽视了蕴涵于真实社会网络边权信息中丰富的语义信息.目前普遍使用的基于模块性最大化的社团挖掘算法倾向于将小社团合并,这使得语义上丰富的小社团容易湮灭于基于拓扑结构信息所挖掘出的大社团中.而挖掘出这些隐含于大社团中的有着丰富语义内涵的小社团对于加深社会网络语义层面的理解有着重要作用.为此,提出一个接近线性复杂度的有权网络社团挖掘算法.通过充分利用权重信息,算法可以将社会网络划分为富含语义信息的粒度较细且相对较小的隐含社团.通过对基于DBLP作者合作网络的实证分析,证实了新算法的有效性和高效性.     

离散Jaya算法的复杂网络社区发现

社区结构是复杂网络的重要特性之一, 基于模块度的复杂网络社区发现问题是一个NP难度的组合优化问题, 常用启发式算法求解. 最近出现的Jaya算法是求解连续优化问题的一种简单有效的元启发式方法. 本文在遵循Jaya算法按靠近最好解、远离最差解的方式更新种群个体的基础上, 针对复杂网络社区发现问题给出了Jaya算法离散化的策略, 提出一种复杂网络社区发现的离散Jaya算法. 实验表明, 在几个典型真实网络实例和一类人造网络实例上, 与几个经典算法和元启发式算法相比, 本文算法具有求解精度高、能自动确定社区数目等优点.