Community Detection and Discovery in Deterministic and Uncertain Networks

• Author / Creator

  Zafarmand, Mohammadmahdi

• Many structures in different areas of science can be modeled with graphs containing nodes and edges, which represent the entities of the model and the relationship between them, respectively. Community detection and discovery are two important tasks in Social Network Analysis, which try to find groups of nodes within a graph such that they are densely connected inside and loosely connected to the rest of the network. A community detection algorithm finds all such characterized structures altogether. In contrast, a community discovery method takes an individual node in the network and finds all other network nodes that belong to the same group as the given node.

  Before, networks were graphs with deterministic nodes and edges, which we were sure of whether they exist or not. Recently uncertainty in collected information makes us model the problems with probabilities (different types of uncertainty may exist in a network, but in this document, we focus only on the probability of edges). Furthermore, networks can have nodes that belong to more than one community. In such cases, we call them Networks with Overlapping Communities. In this document, we try to answer two essential questions of social network analysis, community detection and discovery, in social networks in the presence of deterministic and uncertain edges.

  A part of this work is assigned to evaluate and improve on existing methods in order to make it possible to use them on networks that have probabilistic edges or have overlapping communities.

• Subjects / Keywords

  • Community Discovery
  • Social Network Analysis
  • Deterministic and Uncertain Networks
  • Community Detection

• Graduation date

  Fall 2020

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-aa6d-zp04

• License

  Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.