Complex Network Analysis with Edge Uncertainty

• Author / Creator

  Zhang, Chi

• Many datasets can be represented as networks or graphs, where sets of nodes are joined together in pairs by links or edges. In the past, many works have been done on complex network analysis in deterministic graphs, graphs where the network structure is exactly and deterministically known. Recently, in many cases, uncertainty or imprecise information becomes a critical impediment to understanding and effectively utilizing the information contained in such graphs. There are many kinds of uncertainty in networks, such as edge uncertainty, node uncertainty, direction uncertainty and weight uncertainty. The problem of complex network analysis with uncertainty has become increasingly important. However, only a few studies take uncertainty into consideration. In this thesis, we mainly focus on networks with edge uncertainty, which means the existence of some edges is uncertain. We propose efficient algorithms to solve problems such as entity ranking, link prediction and local community detection for networks with edge uncertainty. Due to the limited number of publicly available uncertain network datasets, we put forward a way to generate uncertain networks for evaluation purposes. Finally, we evaluate our algorithms using existing ground truth as well as based on common metrics to show the effectiveness of our proposed approaches.

• Subjects / Keywords

  • uncertainty
  • complex network
  • community detection
  • entity ranking
  • link prediction

• Graduation date

  Spring 2018

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R37S7J75S

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