Logical Clustering of Similar Vertices in Complex Real-World Networks

We show that vertices part of a physical cluster (determined per the edges that connect the vertices) in a complex real-world network need not be similar on the basis of the values incurred for node-level metrics (say, centrality metrics). We adapt a recently proposed approach (based on unit-disk graphs) to determine logical clusters comprising of vertices of similar values for node-level metrics, but need not be physically connected to each other. We use the Louvain algorithm to determine both the physical and logical clusters on the respective graphs. We employ the Silhouette Index measure to evaluate the similarity of the vertices in the physical and logical clusters. When tested on a suite of 50 social and biological network graphs on the basis of neighborhood and/or shortest path-driven centrality metrics, we observe the Silhouette Index of the logical clusters to be significantly larger than that of the physical clusters.