I have two graphs graphs I know it isn't bipartite, but I need to calculate which one is closest to being bipartite, it is related with bipartivity in network. To define a measure of network bipartivity is based on the concept of closed walks. the bipartivity is defined of G as: bipartivity definition is the sum of all closed walks of diferent lengths in the network starting and ending at each vertex of G.
My idea is to calculte te eigenvalues of each graph and do bipartivity eq I`m right?
thanks a lot.
With $|V(G)|=N$, The subgraph centralization measure can be defined as a weighted sum of all closed-walks (CWs) of length $\ell$ in the network, $\mu_\ell$ , which is related to graph eigenvalues as follows :
$$ \langle SC \rangle = \frac{1}{N} \sum_\ell \frac{\mu_\ell}{\ell !} = \sum_{j=1}^N e^{\lambda_j}$$
This can be expressed as the sum of two contributions, one coming from odd and the other from even CWs:
$$ \langle SC \rangle = \frac{1}{N} \sum_{j=1}^N \left(\cosh(\lambda_j) + \sinh(\lambda_j)\right) = \langle SC \rangle_{even} + \langle SC \rangle_{odd}$$
If $G$ is bipartite then it includes no odd closed walks, i.e. $\langle SC \rangle_{odd}=0$ and $$\langle SC \rangle =\langle SC \rangle_{even} = \frac{1}{N} \sum_{j=1}^N \cosh(\lambda_j)$$
Then indeed you can define a measure of the network bipartivity: $$\beta(G) = \frac{\langle SC \rangle_{even}}{\langle SC \rangle} = \frac{\sum_{j=1}^N \cosh(\lambda_j)}{\sum_{j=1}^N e^{\lambda_j}}$$
You have, $\forall G$, $\beta(G)\leq 1$ with equality iif $G$ is bipartite. You also have a desired monotone property $\beta(G) \geq \beta(G+e)$
See this paper by Ernesto Estrada1 and Juan A. Rodríguez-Velázquez for a full description, and the adequate proofs.