Towards Community Search in Uncertain Graphs

• Author / Creator

  Talebirad, Yashar

• 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.

• Subjects / Keywords

  • Social Network Analysis
  • Community Search
  • Large Networks
  • Uncertain Graphs
  • Community Detection

• Graduation date

  Spring 2024

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-dahb-yb02

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.