Graph communities in Neo4j

Abstract

Community discovery is an essential topic in social network analysis since it provides a way for recursively decomposing a large social graph to easily interpretable subgraphs. The implementation of four major community discovery algorithms, namely the Newman–Girvan or Edge Betweeness, the Walktrap, the Louvain, and the CNM as Java analytics over Neo4j is described. Their correctness was evaluated functionally in two real Twitter graphs with vastly different characteristics. This was done on the grounds that a successful structural graph partitioning should eventually be reflected in the network functionality domain. Additionally, most real world graphs lack a list of ground truth communities, rendering a structural verification difficult, while functionality can be easily observed in most cases. Naturally, this renders the evaluation network-specific, as different social networks have different operational characteristics. The primary algorithmic finding was that the Louvain algorithm yields Twitter communities whose distribution size matches closer, in terms of the Kullback–Leibler divergence, the tweet and retweet distributions, with Newman–Girvan, Walktrap, and CNM following in that order.