Community structure in a large-scale transaction network and visualization

Author

Iino, T and Kamehama, K and Iyetomi, H and Ikeda, Y and Ohnishi, T and Takayasu, H and Takayasu, M

Abstract

We analyze a transaction network of about 800 thousand Japanese firms to elucidate its community structure. Finding community in networks means the appearance of dense connected groups of vertices and sparse connections between groups. We adopt modularity as a quality function of communities introduced by Newman. The modularity optimization is one of effective approaches to find community. We first use a bottom-up algorithm, which makes the optimization fast by using a greedy algorithm. For the community extraction, the greedy algorithm is widely used, however, may not sufficiently optimize modularity because the optimization tends to be trapped by a local maximum especially for large-scale networks. Alternatively we propose a top-down algorithm with implementation of an annealing method and compare effectiveness of the two algorithms. We also compare the results of the community analysis with images of network structure visualized by molecular dynamics method. The vertices belonging to the same community are spatially located close to each other. The community structure determined by the modularity optimization is well reproduced in the network structure obtained by molecular dynamics.