Community Structure in Complex Networks

• Author / Creator

  Zamani Gharaghooshi, Shiva

• There is no shortage of community mining algorithms for discovering structure in complex information networks; most with unique advantages, however, all with drawbacks, including efficiency, correctness, resolution limit, and field of view limit. We introduce a novel efficient approach for community detection based on the notion of edge strength and a formal definition of the notion of community. We consider that there are two types of links in a graph: links that run between communities whose removal may divide the graph into disconnected subgraphs that we refer to as weak links, and links that are inside communities whose removal would not change graph connectivity, that we refer to as strong links. We put forward a new objective function, called SIWO (for Strong In, Weak Out), which encourages adding strong links to the communities while avoiding weak links. Optimizing this function allows us to discover dense subgraphs from which qualified communities that comply with the definition are extracted. This process allows us to effectively discover communities in social networks without the resolution and field of view limit problems some popular approaches, considered the state of the art, suffer from. Moreover, time complexity of our method, which piggybacks on the optimization of Louvain, known to be very efficient, is linear in the number of edges. We experimentally demonstrate the effectiveness of our approach on various real and artificial datasets with large and small communities to show the resilience to the resolution and field of view limits, including large size networks having million edges.

• Subjects / Keywords

  • Graph Analysis
  • Social Network Analysis
  • Community Mining

• Graduation date

  Fall 2018

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R3XP6VK3T

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