IDENTIFICATION OF COMMUNITY STRUCTURE IN NETWORKS USING HIGHER ORDER NEIGHBORHOOD CONCEPTS
Abstract
The identification of community structures in networks is investigated within a framework based on the concepts of higher order neighborhoods and neighborhood matrix 
. This procedure is of relevance especially for networks representing evolutionary situations, since several evidences show that they are assembled from pre-existing smaller structures, rather than by the mere adhesion of individual nodes. We proceed within the successive elimination of the links with largest betweenness degree. The effect of erasing a link at step k is quantified by the distance between 
and 
, which describe the network neighborhoods prior and after the kth link elimination. For modular networks, this measure is characterized by a very long sequence of sharp peaks, following a much more complete cascade of cluster splitting. The evidences indicate that this method identifies a more precise description of smaller communities splitting than the one based on modularity function.
