San Jose State University
Online Local Communities.
Degree: MS, Computer Science, 2019, San Jose State University
A community in a network is a group of nodes that are densely and closely connected to each other, get sparsely connected to the nodes outside the community. Finding communities in a large network helps solve many real-world problems. But detecting such communities in a complex network by focusing on the whole network is not feasible. Instead, we focus on finding communities around one or more seed node(s) of interest. Therefore, in this project, we find local communities. Moreover, we consider the online setting where the whole graph is unknown in the beginning and we get a stream of edges, i.e., pair of nodes, or a stream of higher order structures, i.e., triangles of nodes.
We created a new dataset that consists of web pages and their links by using the Internet Archive. We extended an existing online local graph community detection algorithm, called COEUS, for higher order structures such as triangles of nodes. We provide experimental results and comparison of the existing method and our proposed method using two public datasets, the Amazon and the DBLP as well as for our new Webpages dataset. In the experimental results, we see that the proposed method performs better than the existing method for one out of three test cases for the public dataset but not for our Webpages dataset. This is because the Webpages dataset has a large number of nodes with degree 1 which poses a problem for modified COEUS because it takes triangles as an input stream.
Advisors/Committee Members: Katerina Potika, Christopher Pollett, Sami Khuri.
Subjects/Keywords: Community detection; Local graph clustering; Online com- munity; Theory and Algorithms
to Zotero / EndNote / Reference
APA (6th Edition):
Murali, M. (2019). Online Local Communities. (Masters Thesis). San Jose State University. Retrieved from https://scholarworks.sjsu.edu/etd_projects/723
Chicago Manual of Style (16th Edition):
Murali, Mrudula. “Online Local Communities.” 2019. Masters Thesis, San Jose State University. Accessed June 24, 2019.
MLA Handbook (7th Edition):
Murali, Mrudula. “Online Local Communities.” 2019. Web. 24 Jun 2019.
Murali M. Online Local Communities. [Internet] [Masters thesis]. San Jose State University; 2019. [cited 2019 Jun 24].
Available from: https://scholarworks.sjsu.edu/etd_projects/723.
Council of Science Editors:
Murali M. Online Local Communities. [Masters Thesis]. San Jose State University; 2019. Available from: https://scholarworks.sjsu.edu/etd_projects/723