Show simple item record

dc.contributor.advisorBader, David
dc.contributor.authorGodbole, Pushkar J.
dc.date.accessioned2016-05-27T13:25:16Z
dc.date.available2016-05-27T13:25:16Z
dc.date.created2016-05
dc.date.issued2016-05-10
dc.date.submittedMay 2016
dc.identifier.urihttp://hdl.handle.net/1853/55065
dc.description.abstractAgglomerative Clustering techniques work by recursively merging graph vertices into communities, to maximize a clustering quality metric. The metric of Modularity coined by Newman and Girvan, measures the cluster quality based on the premise that, a cluster has collections of vertices more strongly connected internally than would occur from random chance. Various fast and efficient algorithms for community detection based on modularity maximization have been developed for static graphs. However, since many (contemporary) networks are not static but rather evolve over time, the static approaches are rendered inappropriate for clustering of dynamic graphs. Modularity optimization in changing graphs is a relatively new field that entails the need to develop efficient algorithms for detection and maintenance of a community structure while minimizing the “Size of change” and computational effort. The objective of this work was to develop an efficient dynamic agglomerative clustering algorithm that attempts to maximize modularity while minimizing the “size of change” in the transitioning community structure. First we briefly discuss the previous memoryless dynamic reagglomeration approach with localized vertex freeing and illustrate its performance and limitations. Then we describe the new backtracking algorithm followed by its performance results and observations. In experimental analysis of both typical and pathological cases, we evaluate and justify various backtracking and agglomeration strategies in context of the graph structure and incoming stream topologies. Evaluation of the algorithm on social network datasets, including Facebook (SNAP) and PGP Giant Component networks shows significantly improved performance over its conventional static counterpart in terms of execution time, Modularity and Size of Change.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectDynamic graphs
dc.subjectAgglomeration
dc.subjectClustering
dc.subjectModularity
dc.subjectSocial networks
dc.subjectCommunity detection
dc.subjectStinger
dc.subjectStreaming algorithms
dc.titleAgglomerative clustering for community detection in dynamic graphs
dc.typeThesis
dc.description.degreeM.S.
dc.contributor.departmentComputational Science and Engineering
thesis.degree.levelMasters
dc.contributor.committeeMemberRiedy, Jason
dc.contributor.committeeMemberDilkina, Bistra
dc.date.updated2016-05-27T13:25:16Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record