IDENTIFICATION OF COMMUNITY STRUCTURE IN NETWORKS USING HIGHER ORDER NEIGHBORHOOD CONCEPTS.

The identification of community structures in networks is investigated within a framework based on the concepts of higher order neighborhoods and neighborhood matrix $\hat{M}$. 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 $\hat{M}^{k-1}$ and $\hat{M}^{k}$, 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. [ABSTRACT FROM AUTHOR]