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. / A Dissertation submitted to the Department of Computer Science in partial fulfillment of the requirements
for the degree of Doctor of Philosophy. / Fall Semester 2017. / November 6, 2017. / Community Detection, Community Search, Graph Embedding, Graph Mining, Indexing / Includes bibliographical references. / Peixiang Zhao, Professor Directing Dissertation; Washington Mio, University Representative; Piyush
Kumar, Committee Member; Xiuwen Liu, Committee Member.
| Identifer | oai:union.ndltd.org:fsu.edu/oai:fsu.digital.flvc.org:fsu_604947 |
| Contributors | Akbas, 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 departmentdgg) |
| Publisher | Florida State University |
| Source Sets | Florida State University |
| Language | English, English |
| Detected Language | English |
| Type | Text, text, doctoral thesis |
| Format | 1 online resource (115 pages), computer, application/pdf |
Page generated in 0.0178 seconds