Research On Dynamic Community Search In Large Social Networks

With the rapid development of mobile computing,social network search has become an increasingly popular research topic among scholars.Research related to social network search has extensive applications in various fields such as advertising placement,interest recommendation,community organization,and group buying.Communities are typically composed of nodes representing individuals or entities,with tight internal connections and sparse external connections.Dynamic communities refer to the relationships between nodes or within nodes in the original community that change over time.In real-world applications,dynamic community search often only focuses on searching for a specific homogeneous group of users with the same interests or living in the same geographical area,neglecting the mining of historical user interaction data within the community.This thesis introduces two properties,namely heterogeneous edges and time windows,to address the challenges of dynamic community search.It aims to explore the relationships among nodes within the community by constructing two novel index structures,enabling fast retrieval of communities that meet predefined criteria.The specific research of this thesis is as follows:(1)To tackle the issues of node dynamics and community search efficiency in dynamic social networks with different attribute nodes,this thesis proposes the heterogeneous edge index structure,index maintenance algorithm,and local search algorithm.Firstly,assuming that nodes possess different geographical attributes,the connections between nodes in different regions are defined as heterogeneous edges,transforming the dynamic community search problem into a community search problem that involves heterogeneous edges.Secondly,the EDC-tree index maintenance algorithm is designed,where each level of the index structure contains corresponding edge attributes,and the index does not need to be reconstructed during the dynamic changes of the community.By using pruning techniques,only the neighboring and expanding nodes of the query node are searched,simplifying the community search space.Finally,experimental results validate the effectiveness of the index maintenance algorithm and the efficiency improvement of the local search algorithm,which outperforms the state-of-the-art algorithm by 13%.(2)For dynamic social networks with time and distance attributes,this thesis addresses the problem of searching for communities within a specified time range and proposes the TDC index structure and TDC-Query algorithm.Firstly,the temporal edges of the social network dataset are organized and arranged in natural order of growth.The TDC index structure enables fast determination of whether a node exists within a given time window and quickly checks if the distance to neighboring nodes exceeds a given threshold,iteratively removing nodes that do not meet the aforementioned conditions.To accelerate dynamic community search,the TDCQuery algorithm simplifies the search process using a binary search approach.Finally,through experimental comparisons with three different search methods,the proposed index structure is shown to effectively retrieve nodes that meet the criteria,achieving a 15% improvement in query efficiency compared to other state-of-the-art algorithms.This thesis conducts extensive comparative experiments on real social network datasets,demonstrating the efficiency and effectiveness of the proposed index structures and algorithms,and provides insights for future research directions.