Community structure in a large-scale transaction network and visualization

• Published in: Journal of physics. Conference series 2010-04, Vol.221 (1), p.012012
• Main Authors: Iino, T, Kamehama, K, Iyetomi, H, Ikeda, Y, Ohnishi, T, Takayasu, H, Takayasu, M
• Format: Article
• Language: English
• Subjects: Algorithms; Apexes; Greedy algorithms; Modularity; Molecular dynamics; Molecular structure; Optimization; Physics
• ISSN: 1742-6596; 1742-6588; 1742-6596
• DOI: 10.1088/1742-6596/221/1/012012

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.