You are here

Community Search and Detection on Large Graphs

Title: Community Search and Detection on Large Graphs.
Name(s): Akbas Da Silvia, Esra, author
Zhao, Peixiang, professor directing dissertation
Mio, Washington, university representative
Kumar, Piyush, committee member
Liu, Xiuwen, 1966-, committee member
Florida State University, degree granting institution
College of Arts and Sciences, degree granting college
Department of Computer Science, degree granting department
Type of Resource: text
Genre: Text
Doctoral Thesis
Issuance: monographic
Date Issued: 2017
Publisher: Florida State University
Place of Publication: Tallahassee, Florida
Physical Form: computer
online resource
Extent: 1 online resource (115 pages)
Language(s): English
Abstract/Description: Modern science and technology have witnessed in the past decade a proliferation of complex data that can be naturally modeled and interpreted as graphs. In real-world networked applications, the underlying graphs oftentimes exhibit fundamental community structures supporting widely varying interconnected processes. Identifying communities may offer insight on how the network is organized. In this thesis, we worked on community detection and search problems on graph data. Community detection (graph clustering) has become one of the most well-studied problems in graph management and analytics, the goal of which is to group vertices of a graph into densely knitted clusters with each cluster being well separated from all the others. Classic graph clustering methods primarily take advantage of topological information of graphs to model and quantify the proximity between vertices. With the proliferation of rich, heterogeneous graph contents widely available in real-world graphs, such as user profiles in social networks, it becomes essential to consider both structures and attributive contents of graphs for better quality graph clustering. On the other hand, existing community detection methods focus primarily on discovering communities in an apriori, top-down manner with the only reference to the input graph. As a result, all communities have to be exhaustively identified thus incurring expensive time/space cost and a huge amount of fruitless computation, if only a fraction of them are of special interest to end-users. In many real-world occasions, however, people are more interested in the communities pertaining to a given vertex. In our first project, we work on attributed graph clustering problem. We propose a graph embedding approach to cluster content-enriched, attributed graphs. The key idea is to design a unified latent representation for each vertex of a graph such that both the graph connectivity and vertex attribute proximity within the localized region of the vertex can be jointly embedded into a unified, continuous vector space. As a result, the challenging attributed graph clustering problem is cast to the traditional data clustering problem. In my second and third projects, we work on a query-dependent variant of community detection, referred to as the community search problem. The objective of community search is to identify dense subgraphs containing the query vertices. We study the community search problem in the truss-based model aimed at discovering all dense and cohesive k-truss communities to which the query set Q belongs. We introduce a novel equivalence relation, k-truss equivalence, to model the intrinsic density and cohesiveness of edges in k-truss communities and based on this equivalence we create 2 different space-efficient, truss-preserving index structure, EquiTruss and TEQ. Community search for one query or multiple queries can thus be addressed upon EquiTruss and TEQ without repeated, time-demanding accesses to the original graph, G, which proves to be theoretically optimal. While query set includes one query vertex in our first project, it includes multiple query vertices in our second project. As a summary, to get better quality on attributed graph clustering, the attribute-aware cluster information is well preserved during graph embedding. While we use Skip-Gram method for embedding, there are other embedding methods. We can use them to see the effect of different embedding methods on attributed graphs. In addition, our index structure is good for community search on large graphs without considering attribute information. Using attribute information in addition to the structure may give better communities for given query nodes. So, we can update our index structure to support community search on attributed graphs.
Identifier: FSU_FALL2017_Akbas_fsu_0071E_14173 (IID)
Submitted Note: A Dissertation submitted to the Department of Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy.
Degree Awarded: Fall Semester 2017.
Date of Defense: November 6, 2017.
Keywords: Community Detection, Community Search, Graph Embedding, Graph Mining, Indexing
Bibliography Note: Includes bibliographical references.
Advisory Committee: Peixiang Zhao, Professor Directing Dissertation; Washington Mio, University Representative; Piyush Kumar, Committee Member; Xiuwen Liu, Committee Member.
Subject(s): Computer science
Persistent Link to This Record:
Owner Institution: FSU

Choose the citation style.
Akbas Da Silvia, E. (2017). Community Search and Detection on Large Graphs. Retrieved from