时序网络中短时社区搜索方法研究

时序网络中的社区搜索问题旨在寻找符合一定时序规律的社区.短时交互特性作为时序网络的一种重要时序特征,相比于长期社区更具研究价值,可用于有效挖掘网络中核心的时序紧密结构.现有工作大多研究了时序社区的持续性、突变性、周期性等现象,尚无法建模时序社区的短时特性.针对现有工作难以满足上述需求的现状,提出top-k短时社区搜索这...

Research on Short-Time Community Search in Temporal Networks

The community search problem in temporal social networks aims to find communities that can satisfy certain temporal phenomena.Short-time interactions between members are important temporal features of social networks.Compared to long-term communities,communities formed in a short time have more important research interests,as they can be used to effectively discover the potential core short-time structure with cohesiveness guaranteed in the network.However,most recent works focus on studying the phenomena of the persistent property,the bursting property and the periodic property of the temporal communities,these works fail to model the short-time phenomenon in the temporal network.In view of the current situation that it is difficult for existing works to meet the above requirements,a new problem of top-k short-time community search is proposed.At the same time,a novel and effective solution is provided for finding short-time communities in complex networks.Firstly,in order to depict the short-time phenomenon in the temporal network,a formal definition ofδshort-time community is proposed to explore the short-time structure,and a method for calculating the time interval of a temporal community which is formed under different time interactions is given to precisely measure the short-time indicator.Secondly,the top-kδshort-time community search algorithm ShrimeCS is proposed.The conditions to judge the minimalδshort-time community and top-kδshort-time community are carefully analyzed and discussed.After that,theδbasic block is proposed.It can be used to find the minimalδshort-time community with the help of the minimalδshort-time community judgment condition.Furthermore,the concept ofδstrong block is proposed to avoid redundancy during subgraph expansion.Through utilizing the non-overlapping property of theδstrong block,the time cost can be largely reduced.In addition,we analyze and propose two heuristic approaches,which are the global time interval-based optimization approach and the progressive time interval-based optimization approach,to further improve the efficiency of ShrimeCS.Compared to the original algorithms,the two proposed optimization approaches can improve the optimization rate during the searching process by over 64.2%.Then,the experiments are conducted on five real-world datasets(i.e.,Email,Msg,Math,SuperUser and DBLP)and three synthetic datasets.At the same time,a new metric,clustering factor(i.e.,CT-factor),which is to evaluate the closeness of the interaction between two members in the temporal community,is proposed.The experimental results show that the communities found by ShrimeCS have better short-time features compared to other baselines.Moreover,the results demonstrate that the proposed optimization approaches(i.e.,the global time interval-based optimization approach and progressive time interval-based optimization approach)can reduce the time cost by 17.16%.The case study in a real-world application scenario shows that the top-kδshort-time communities which are found by ShrimeCS can capture the dynamics of the time interval shifted in the community,and it is therefore beneficial to explore the community evolution through the time dimension.Finally,the correctness of ShrimeCS is verified,and the good scalability of ShrimeCS is demonstrated.