- author = "Zheng Gao",
- title = "Community Detection in Graphs",
- school = "Luddy School of Informatics, Computing, and Engineering, Indiana University",
- year = "2020",
- address = "Bloomington, USA",
- month = jun,
- keywords = "genetic algorithms, genetic programming, genetic pruning",
-
URL = "
https://ils.indiana.edu/programs/phd-information-science/dissertation-list.html",
-
URL = "https://scholarworks.iu.edu/iuswrrest/api/core/bitstreams/da9485ea-3aaa-42a9-8db3-9f2b35c8ebc5/content",
- size = "204 pages",
-
abstract = "Community detection has always been one of the
fundamental research topics in graph mining. As a type
of unsupervised or semi-supervised approach, community
detection aims to explore node high-order closeness by
leveraging graph topological structure. By grouping
similar nodes or edges into the same community while
separating dissimilar ones apart into different
communities, graph structure can be revealed in a
coarser resolution. It can be beneficial for numerous
applications such as user shopping recommendation and
advertisement in e-commerce, protein-protein
interaction prediction in the bioinformatics, and
literature recommendation or scholar collaboration in
citation analysis.
However, identifying communities is an ill-defined problem. Due to the No Free Lunch theorem (NFL), there is neither gold standard to represent perfect community partition nor universal methods that are able to detect satisfied communities for all tasks under various types of graphs. To have a global view of this research topic, I summarize state-of-art community detection methods by categorizing them based on graph types, research tasks and methodology frameworks. As academic exploration on community detection grows rapidly in recent years, I hereby particularly focus on the state-of-art works published in the latest decade, which may leave out some classic models published decades ago.
Meanwhile, three subtle community detection tasks are proposed and assessed in this dissertation as well. First, apart from general models which consider only graph structures, personalized community detection considers user need as auxiliary information to guide community detection. In the end, there will be fine-grained communities for nodes better matching user needs while coarser-resolution communities for the rest of less relevant nodes. Second, graphs always suffer from the sparse connectivity issue. Leveraging conventional models directly on such graphs may hugely distort the quality of generate communities. To tackle such a problem, cross-graph techniques are involved to propagate external graph information as a support for target graph community detection. Third, graph community structure supports a natural language processing (NLP) task to depict node intrinsic characteristics by generating node summarizations via a text generative model.
The contribution of this dissertation is threefold. First, a decent amount of researches are reviewed and summarized under a well-defined taxonomy. Existing works about methods, evaluation and applications are all addressed in the literature review. Second, three novel community detection tasks are demonstrated and associated models are proposed and evaluated by comparing with state-of-art baselines under various datasets. Third, the limitations of current works are pointed out and future research tracks with potentials are discussed as well.",
-
notes = "number 205 Is this GP?
Supervisor: Xiaozhong Liu",
