Blog
About

  • Record: found
  • Abstract: found
  • Article: found
Is Open Access

Use of Eigenvalue and Eigenvectors to Analyze Bipartivity of Network Graphs

Preprint

Read this article at

Bookmark
      There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

      Abstract

      This paper presents the applications of Eigenvalues and Eigenvectors (as part of spectral decomposition) to analyze the bipartivity index of graphs as well as to predict the set of vertices that will constitute the two partitions of graphs that are truly bipartite and those that are close to being bipartite. Though the largest eigenvalue and the corresponding eigenvector (called the principal eigenvalue and principal eigenvector) are typically used in the spectral analysis of network graphs, we show that the smallest eigenvalue and the smallest eigenvector (called the bipartite eigenvalue and the bipartite eigenvector) could be used to predict the bipartite partitions of network graphs. For each of the predictions, we hypothesize an expected partition for the input graph and compare that with the predicted partitions. We also analyze the impact of the number of frustrated edges (edges connecting the vertices within a partition) and their location across the two partitions on the bipartivity index. We observe that for a given number of frustrated edges, if the frustrated edges are located in the larger of the two partitions of the bipartite graph (rather than the smaller of the two partitions or equally distributed across the two partitions), the bipartivity index is likely to be relatively larger.

      Related collections

      Author and article information

      Journal
      2014-12-16
      2016-01-19
      1412.6155

      http://arxiv.org/licenses/nonexclusive-distrib/1.0/

      Custom metadata
      A paper with a similar idea has been published earlier. I was not aware of this before. Now that, I have come to know about this, I am withdrawing my paper from arXiv
      cs.SI physics.soc-ph

      Social & Information networks, General physics

      Comments

      Comment on this article