Three Community Detection Using Mark Newman's Modularity (2008)

Undergraduate: Thomas Richardson

Faculty Advisor: Peter Mucha
Department: Applied Sciences

---

From the adjacency matrix for a system of nodes in a network, standard methods can be used to compute eigenvalues. These eigenvalues can then be used to approximate placement of nodes into communities, as described by Mark Newman. The number of eigenvalues used determines the maximum number of possibly communities one has information about. For example, with 2 eigenvalues, one has enough information to sort the nodes approximately into a maximum of three communities; with 3, 4 communities, etc. These eigenvalues, though, only provide 'guesses' as to where the nodes belong based on a scoring termed modularity. It is very likely that the maximum modularity will not be obtained through placement of nodes using only one or two eigenvalues. Therefore, after sorting nodes using eigenvalues, the implementation of a fine-tuning algorithm is desirable. These two methods used in tandem, a rapid initial sort using only eigenvalues and a selectively exhaustive fine tuning method, result in an overall rather speedy method for obtaining accurate community detection based on Newman's modularity score. Specifically in this presentation, three-way community detection will be discussed.