Research On Community Search Algorithm On Directed Weighted Graph

This paper investigates the problem of community search in directed weighted graphs,where the goal is to find subgraphs with high cohesion and inclusion of query points.This problem has wide applications in social network analysis,recommendation systems,knowledge graph mining,and bioinformatics.In practical applications,the results of community search not only need to consider the cohesiveness of the subgraph but also its influence.However,existing methods only consider the cohesiveness of the subgraph and ignore its influence.For example,in a social network,the influence of a community is a dimension that measures user activity and trustworthiness,which plays a crucial role in social networks.Therefore,there is a need for a new community search method that can comprehensively consider these factors to find communities with high influence more accurately.The paper proposes two online algorithms for community search on vertex-weighted directed graphs: Top-Down Truss Community Search(TDT-CS)based on top-down thinking and Bottom-Up Truss Community Search(BUT-CS)based on bottom-up thinking.These two algorithms are designed for community search on directed weighted graphs and consider both the cohesiveness of the result subgraph and its overall influence to meet the needs of practical application scenarios.Furthermore,the paper proposes three optimization strategies to accelerate the efficiency of community search:(1)candidate community solution methods based on Truss Guard index,(2)result generation strategy Batch Extension Vertex Insertion(HBVI),and(3)result generation strategy Smart Insert based on HBVI.The Truss Guard index significantly reduces the calculation time of finding candidate communities by pre-indexing the graph.HBVI optimizes the expensive operation cost caused by online algorithm expansion during result generation.Smart Insert further reduces the scale of graph expansion based on HBVI.Finally,to verify the efficiency of the proposed algorithms,experiments are conducted on five real-world directed networks.Under different threshold requirements,the experimental results show that the proposed algorithms have good performance and scalability.