Edge Similarity Index for Complex Network Analysis

  • Natarajan Meghanathan Jackson State University
Keywords: Edge Similarity, Centrality Metrics, Threshold Distance, Binary Search Algorithm


We propose a novel network-level metric called Edge Similarity Index (ESI) to quantify the extent of similarity between any two edges of a complex network with respect to the values for a node-level metric (like centrality metric) of its end vertices. To assess the ESI measure for a complex real-world network with respect to a node-level metric, we propose to first construct a logical network whose vertices are the actual edges of the network (with coordinates corresponding to the normalized node-level metric values of the actual end vertices) and there exists a (logical) edge between two logical vertices if the Euclidean distance between their corresponding coordinates is within a threshold distance. We propose a binary search algorithm to determine the minimum value for this threshold distance () that would result in a connected logical unit-disk graph; the ESI value for the complex network is then computed as . The ESI values range from 0.0 to 1.0; the larger the ESI value with respect to a node-level metric, we claim that more similar are any two edges in the network with respect to the node-level metric values for their end vertices.

How to Cite
Meghanathan, N. (2020). Edge Similarity Index for Complex Network Analysis. International Journal of Combinatorial Optimization Problems and Informatics, 11(3), 76-96. Retrieved from https://ijcopi.org/ojs/article/view/129