Rezvani, Mojtaba
Description
Vertices in complex networks can be grouped into communities,
where vertices inside communities are densely connected to each
other and vertices from one community are sparsely connected to
vertices in other communities. This is the so-called community
structure in complex networks. Identifying the community
structure of networks has many applications, ranging from data
mining, webpage clustering and market- ing to extracting proteins
with the same...[Show more] functionality in protein-protein-interaction
networks and beyond.
This thesis addresses a number of the primary problems
surrounding community structure in large-scale networks. These
problems generally revolve around two of the principal challenges
of the area, accuracy and soundness of modelling and scala-
bility to real-world networks. The problems include identifying
top-k structural hole spanners, detecting the hierarchy of
communities, detecting overlapping communi- ties, and community
search in large-scale complex networks. The thesis formally de-
fines the cohesive hierarchies of communities in complex
networks. Since scalability is a major challenge for cohesive
hierarchical community detection, the thesis incor- porates a
network sparsification technique to leverage the network size and
finds co- hesive hierarchies of communities in large-scale
complex networks. The problem of identifying top-k structural
hole spanners is formally defined in this thesis and several
scalable algorithms have been presented for this problem.
Furthermore, the thesis delves into the problem of overlapping
community detection and proposes an accu- rate fitness metric to
find overlapping communities in large-scale complex networks. The
thesis finally studies the problem of community search and
introduces a new al- gorithm for community search in complex
networks.
The thesis develops novel models, algorithms, and evaluation
measures for these problems, and presents the experimental
results of these algorithms using real-world datasets, which
outperform considerably on the scalability and accuracy of the
state of the art, in several cases.
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.