Towards Community Search in Uncertain Graphs

Abstract

The representation of real-world relationships and entities through nodes and edges in a network has found wide applicability across diverse scientific fields. At the core of network analysis are the tasks of community detection and community search, which aim to identify distinct groups within a graph. While community detection partitions the graph on a global scale, community search focuses on a specific node or group of nodes to discover a cohesive subgraph in their vicinity. Traditionally, these networks were represented as deterministic graphs with clearly defined nodes and edges. However, as networks grow in scale, analyzing these networks becomes more challenging. Coupled with this, the emergence of uncertainty in data collection has necessitated a shift towards probabilistic modeling of these relationships, presenting a suite of new complexities and challenges. In response to these challenges, this thesis first focuses on enhancing the SIWO algorithm, initially designed for community mining in deterministic graphs, to make it suitable for processing very large graphs. We introduce a methodology to convert large graphs into a format that is more manageable by local community search algorithms, ensuring efficient processing without the need to store entire networks in main memory. This is complemented by the development of data structures and optimization techniques specifically designed to manage and process large-scale network data efficiently. Building upon these enhancements, we then present USIWO, a scalable and local algorithm for community search in unweighted uncertain graphs with edge uncertainty. USIWO starts from a single node or set of nodes and incrementally adds “suitable” adjacent nodes one at a time, until it rapidly finds the core of a community even in very large uncertain networks.