Graph Isomorphism is one of the classical problems of graph theory for which no deterministic
polynomial-time algorithm is currently known, but has been neither proven to be NP-complete. Several
heuristic algorithms have been proposed to determine whether or not two graphs are isomorphic (i.e.,
structurally the same). In this paper, we analyze the discriminating power of the well-known centrality
measures on real-world network graphs and propose to use the sequence (either the non-decreasing or
non-increasing order) of eigenvector centrality (EVC) values of the vertices of two graphs as a precursor
step to decide whether or not to further conduct tests for graph isomorphism. The eigenvector centrality of
a vertex in a graph is a measure of the degree of the vertex as well as the degrees of its neighbors. As the
EVC values of the vertices are the most distinct, we hypothesize that if the non-increasing (or nondecreasing) order of listings of the EVC values of the vertices of two test graphs are not the same, then the
two graphs are not isomorphic. If two test graphs have an identical non-increasing order of the EVC
sequence, then they are declared to be potentially isomorphic and confirmed through additional heuristics.
We test our hypothesis on random graphs (generated according to the Erdos-Renyi model) and we observe
the hypothesis to be indeed true: graph pairs that have the same sequence of non-increasing order of EVC
values have been confirmed to be isomorphic using the well-known Nauty software.
%0 Journal Article
%1 noauthororeditor
%A Meghanathan, Natarajan
%D 2015
%J International Journal on Foundations of Computer Science & Technology (IJFCST)
%K Centrality Degree Eigenvector Graph Graphs Isomorphism Precursor Random Step.
%N 6
%P 13
%R 10.5121/ijfcst.2015.5601
%T EXPLOITING THE DISCRIMINATING POWER OF THE
EIGENVECTOR CENTRALITY MEASURE TO DETECT
GRAPH ISOMORPHISM
%U https://wireilla.com/papers/ijfcst/V5N6/5615ijfcst01.pdf
%V 5
%X Graph Isomorphism is one of the classical problems of graph theory for which no deterministic
polynomial-time algorithm is currently known, but has been neither proven to be NP-complete. Several
heuristic algorithms have been proposed to determine whether or not two graphs are isomorphic (i.e.,
structurally the same). In this paper, we analyze the discriminating power of the well-known centrality
measures on real-world network graphs and propose to use the sequence (either the non-decreasing or
non-increasing order) of eigenvector centrality (EVC) values of the vertices of two graphs as a precursor
step to decide whether or not to further conduct tests for graph isomorphism. The eigenvector centrality of
a vertex in a graph is a measure of the degree of the vertex as well as the degrees of its neighbors. As the
EVC values of the vertices are the most distinct, we hypothesize that if the non-increasing (or nondecreasing) order of listings of the EVC values of the vertices of two test graphs are not the same, then the
two graphs are not isomorphic. If two test graphs have an identical non-increasing order of the EVC
sequence, then they are declared to be potentially isomorphic and confirmed through additional heuristics.
We test our hypothesis on random graphs (generated according to the Erdos-Renyi model) and we observe
the hypothesis to be indeed true: graph pairs that have the same sequence of non-increasing order of EVC
values have been confirmed to be isomorphic using the well-known Nauty software.
@article{noauthororeditor,
abstract = {Graph Isomorphism is one of the classical problems of graph theory for which no deterministic
polynomial-time algorithm is currently known, but has been neither proven to be NP-complete. Several
heuristic algorithms have been proposed to determine whether or not two graphs are isomorphic (i.e.,
structurally the same). In this paper, we analyze the discriminating power of the well-known centrality
measures on real-world network graphs and propose to use the sequence (either the non-decreasing or
non-increasing order) of eigenvector centrality (EVC) values of the vertices of two graphs as a precursor
step to decide whether or not to further conduct tests for graph isomorphism. The eigenvector centrality of
a vertex in a graph is a measure of the degree of the vertex as well as the degrees of its neighbors. As the
EVC values of the vertices are the most distinct, we hypothesize that if the non-increasing (or nondecreasing) order of listings of the EVC values of the vertices of two test graphs are not the same, then the
two graphs are not isomorphic. If two test graphs have an identical non-increasing order of the EVC
sequence, then they are declared to be potentially isomorphic and confirmed through additional heuristics.
We test our hypothesis on random graphs (generated according to the Erdos-Renyi model) and we observe
the hypothesis to be indeed true: graph pairs that have the same sequence of non-increasing order of EVC
values have been confirmed to be isomorphic using the well-known Nauty software. },
added-at = {2023-04-26T12:44:58.000+0200},
author = {Meghanathan, Natarajan},
biburl = {https://www.bibsonomy.org/bibtex/22be6cf5d51b78d55f56c0ad5615c6587/devino},
doi = {10.5121/ijfcst.2015.5601},
interhash = {0741cbbe6a32b327875bb48385edbf4b},
intrahash = {2be6cf5d51b78d55f56c0ad5615c6587},
issn = {1839-7662},
journal = {International Journal on Foundations of Computer Science & Technology (IJFCST)},
keywords = {Centrality Degree Eigenvector Graph Graphs Isomorphism Precursor Random Step.},
language = {ENGLISH},
month = nov,
number = 6,
pages = 13,
timestamp = {2023-04-26T12:44:58.000+0200},
title = {EXPLOITING THE DISCRIMINATING POWER OF THE
EIGENVECTOR CENTRALITY MEASURE TO DETECT
GRAPH ISOMORPHISM},
url = {https://wireilla.com/papers/ijfcst/V5N6/5615ijfcst01.pdf},
volume = 5,
year = 2015
}