Community Search (CS) aims to enable online and personalized discovery of communities. Recently, attention to the CS problem in directed graphs (di-graph) needs to be improved despite the extensive study conducted on undirected graphs. Nevertheless, the existing studies are plagued by several shortcomings, e.g., Achieving high-performance CS while ensuring the retrieved community is cohesive is challenging. This paper uses the D-truss model to address the limitations of investigating the CS problem in large di-graphs. We aim to implement millisecond-level D-truss CS in di-graphs by building a summarized graph index. To capture the interconnectedness of edges within D-truss communities, we propose an innovative equivalence relation known as D-truss-equivalence, which allows us to divide the edges in a di-graph into a sequence of super nodes (s-nodes). These s-nodes form the D-truss-equivalencebased index, DEBI, an index structure that preserves the truss properties and ensures efficient space utilization. Using DEBI, CS can be performed without time-consuming access to the original graph. The experiments indicate that our method can achieve millisecond-level D-truss community query while ensuring high community quality. In addition, dynamic maintenance of indexes can also be achieved at a lower cost. Our code is available athttps://github.com/XieCanhao04/DEBI.

Community search is a derivative of community detection that enables online and personalized discovery of communities and has found extensive applications in massive real-world networks. Recently, there needs to be more focus on the community search issue within directed graphs, even though substantial research has been carried out on undirected graphs. The recently proposed D-truss model has achieved good results in the quality of retrieved communities. However, existing D-truss-based work cannot perform efficient community searches on large graphs because it consumes too many computing resources to retrieve the maximal D-truss. To overcome this issue, we introduce an innovative merge relation known as D-truss-connected to capture the inherent density and cohesiveness of edges within D-truss. This relation allows us to partition all the edges in the original graph into a series of D-truss-connected classes. Then, we construct a concise and compact index, ConDTruss, based on D-truss-connected. Using ConDTruss, the efficiency of maximum D-truss retrieval will be greatly improved, making it a theoretically optimal approach. Experimental evaluations conducted on large directed graphs certificate the effectiveness of our proposed method.

Community Search (CS) aims to identify densely interconnected subgraphs corresponding to query vertices within a graph. However, existing heterogeneous graph-based community search methods need help identifying cross-group communities and suffer from efficiency issues, making them unsuitable for large graphs. This paper presents a fast community search model based on the Butterfly-Core Community (BCC) structure for heterogeneous graphs. The Random Walk with Restart (RWR) algorithm and butterfly degree comprehensively evaluate the importance of vertices within communities, allowing leader vertices to be rapidly updated to maintain cross-group cohesion. Moreover, we devised a more efficient method for updating vertex distances, which minimizes vertex visits and enhances operational efficiency. Extensive experiments on several real-world temporal graphs demonstrate the effectiveness and efficiency of this solution.