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

时序网络中的社区搜索问题旨在寻找符合一定时序规律的社区.短时交互特性作为时序网络的一种重要时序特征,相比于长期社区更具研究价值,可用于有效挖掘网络中核心的时序紧密结构.现有工作大多研究了时序社区的持续性、突变性、周期性等现象,尚无法建模时序社区的短时特性.针对现有工作难以满足上述需求的现状,提出top-k短时社区搜索这一新问题,为有效发现复杂网络中短时紧密社区提供新的解决思路.首先,针对时序网络中社区的短时特性,提出了δ-短时社区的形式化定义用以刻画短时社区结构.同时,给出了不同时间交互下形成的时序社区的时间跨度计算方式,为衡量短时社区提供一个具体的量化指标.其次,提出了top-kδ-短时社区搜索算法ShrimeCS,分析并讨论了短时社区的判断条件分别用以判断最小δ-短时社区和top-kδ-短时社区,并提出了δ-基本块结构结合判断条件用以找到最小δ-短时社区.此外,进一步提出了强δ-基本块结构以避免在扩展过程中出现子图冗余,从而降低搜索过程的时间开销.还分析了top-kδ-短时社区搜索过程中基于全局时间跨度上界与渐进时间跨度上界优化的启发式计算方法,以进一步加快算法运行效率,搜索优化率相比原算法提高64.2%以上.然后,在5个真实数据集和3个合成数据集上进行了实验,并提出了聚集因子指标用以评估时序社区中成员交互时间的接近程度.实验结果显示,ShrimeCS找到社区的短时性优于基准方法,基于全局时间跨度和渐进时间跨度上界优化可以降低17.16%以上的时间开销.在真实场景中的案例研究表明,ShrimeCS找到的top-kδ-短时社区可以捕捉到社区中时间跨度的变化,可以用来探索社区随时间的演化情况.最后,验证了所提方法的正确性,并表明ShrimeCS算法具有较好的可扩展性.

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.