A note on the Estrada–Hatano communicability algorithm for detecting community structure in complex networks

摘要

Recently Estrada and Hatano proposed an algorithm for the detection of community structure in complex networks using the concept of network communicability. Here we amend this algorithm by eliminating the subjectivity of choosing degree of overlapping and including an additional check of the fitness of detected communities. We show that this amendment can detect some communities which remain undetected by Estrada and Hatano’s algorithm. For instance, let G(p, q) be a graph obtained from two cliques, Kp and Kq(p ⩾ q ⩾ 3), joined by a single edge. It is apparent that this graph contains two communities, namely the two cliques. However, Estrada and Hatano’s algorithm detects only Kq as a community when p is sufficiently larger than q. Our algorithm correctly detects both communities. Also, our method also finds the correct community structure in one of the classic benchmark networks, the Zachary karate club.