ITIC:一种高效的k-影响社区top-r查询算法

ITIC: AN EFFICIENT TOP-R QUERY ALGORITHM FOR K-INFLUENTIAL COMMUNITY

k-影响社区(k-Influential Community, k-IC)是网络中具有较大影响值且无包含关系的最大连通k-core。k-IC的top-r查询的目标是返回影响值较大的前r个k-IC。针对此问题,提出W-D(Weight-Degree)索引用于管理网络。提出k-IC的top-r查询优化算法ITIC(Index-based Top-r Query Algorithm for k-Influential Community),该算法无须频繁计算连通分量,并且从权重较大的节点开始处理,一般只对部分节点进行处理即可求得结果。同时,该算法是渐进输出k-IC,可根据用户需求随时终止算法。通过实验验证所提算法的有效性。实验结果表明,相对于现有算法,ITIC可以显著提高计算效率。

The k-Influential community(k-IC)is the maximum connected k-core in the network that has the large influential value and does not have an inclusive relationship.The goal of the top-r query of k-IC is to return the top r k-ICs with the larger value.To study this problem,we proposed a W-D(Weight-Degree)index to manage the network.We proposed the k-IC top-r query optimization algorithm named ITIC(Index-based Top-r Query Algorithm for k-Influential Community).The algorithm did not need to frequently calculate the connected components,and started processing from the nodes with larger weights.Generally,it only processed part of nodes in the network to obtain the results.At the same time,the algorithm outputted k-IC gradually,and we could terminate it at any time according to the needs of users.The experiments verified the effectiveness of the proposed algorithm.The experimental results show that compared with the existing algorithms,ITIC can significantly improve the computational efficiency.