Force-directed Layout Community Detection
| dc.contributor.author | SONG, Yi | en_US |
| dc.contributor.author | BRESSAN, Stephane | en_US |
| dc.date.accessioned | 2013-05-21T01:33:30Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:07Z | |
| dc.date.available | 2013-05-21T01:33:30Z | en_US |
| dc.date.available | 2017-01-23T07:00:07Z | |
| dc.date.issued | 2013-05-21T01:33:30Z | en_US |
| dc.description.abstract | In this paper, we propose a graph-layout based method for detecting communities in networks. We first project the graph onto a Euclidean space using Fruchterman-Reingold algorithm, a force-based graph drawing algorithm. We then cluster the vertices according to their Euclidean distance. The idea is similar to that of dimension reduction. The graph drawing in two or more dimension provides a heuristic decision as whether vertices are connected by a short path based on their Euclidean distance. We study community detection for both disjoint and overlapping communities. For the case of disjoint communities, we use k-means clustering. For the case of overlapping communities, we use fuzzy-c means algorithm. We evaluate the performance of our different algorithms for varying parameters and number of iterations. We compare the results to several state of the art community detection algorithms, each of which clusters the graph directly or indirectly according to geodesic distance. We show that, for non-trivially small graphs, our method is both effective and efficient. We measure effectiveness using modularity when the communities are not known in advance and precision when the communities are known in advance. We measure efficiency with running time. The running time of our algorithms can be controlled by the number of iterations of the Fruchterman-Reingold algorithm. | en_US |
| dc.format.extent | 404987 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/4144 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | ;TRB5/13 | en_US |
| dc.title | Force-directed Layout Community Detection | en_US |
| dc.type | Technical Report | en_US |