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

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

Neighborhood k-core based Community: Model and Algorithms

Real-world networks often exhibit community structures, and community search is a fundamental task in graph data mining. Existing studies introduced various models to identify communities within networks, such as k-core based models and k-truss based models. Nevertheless, these models typically confine themselves to constraining the number of neighbors of nodes or edges within a community, disregarding the relationships between these neighbors, namely, the neighborhood structure of the nodes. Consequently, the localized density of nodes within communities tends to be low. To address this limitation, this paper integrates the information regarding the neighborhood structure of nodes into the k-core dense subgraph model, thereby introducing a novel neighborhood k-core based community model and defining the density of a community. Based on the novel model, this paper investigates the problem of identifying the single community which outputs the community containing the query node set with the highest community density. In real-life networks, the query nodes may be distributed across multiple disjoint communities. To this end, this paper further studies the problem of multi-community search based on a density threshold. This entails returning multiple communities that encompass the query node set, with each community demonstrating a density no lower than the user-specified threshold. For the problem of identifying the densst single community and the multi-community search based on a density threshold, this paper introduces the concept of edge density with which two basic search algorithms are proposed. To improve the efficiency, two index structures: the index tree and the enhanced index tree structures are devised to support the retrieval of query results in polynomial time. The effectiveness and efficiency of the proposed community model and search algorithms are demonstrated through comparative analyses against basic search algorithms using several different datasets.