How to check if the network data comes from a bipartite network?

Question

If I am having a set of adjacent matrices network data, how can I check if this data come a bipartite network?

Probably by using Matlab?

The data set is huge, can I check it by using the plot of degree distribution? Or the "$\log\log$" plot.

Thanks for helping.

Answer 1

The most straightforward way to check if $G$ is bipartite is to try to $2$-color it: pick a vertex to be in one part (or one color), which tells you what all its neighbors must do, which tells you about all of their neighbors, and so on. Eventually, you either get a conflict or color the graph.

(Or at least color a connected component. If your coloring stops advancing, you pick a vertex in a different connected component and keep going.)

We can do this by breadth-first search. Color a vertex with the first color and add it to the queue. Then repeatedly pick a vertex $v$ off the queue and do the following:

• Look through all of $v$'s neighbors that have already been colored, and make sure there are no conflicts with $v$'s color.
• Look through all of $v$'s neighbors that have not been colored yet, give them the opposite of $v$'s color, and add them to the queue.

If we ever see a conflict, the graph is not bipartite. If the queue is empty but not all vertices have been colored, the graph is disconnected and we start over from an arbitrary uncolored vertex. If all vertices have been colored, the graph is bipartite.

---

Or, if you like, you can think of this as a matrix computation: if $A$ is the adjacency matrix, let $x^{(0)}$ be the vector $(1,0,0,\dots,0)$ and iterate the following procedure: let $y^{(i)} = Ax^{(i)}$ and compute $x^{(i+1)}$ from $y^{(i)}$ by replacing all of its nonzero entries with $1$. Then:

• If $x^{(i+1)}$ and $x^{(i)}$ have a $1$ in the same coordinate (equivalently, if the dot product $\langle x^{(i)}, x^{(i+1)} \rangle$ is nonzero), then the graph is not bipartite; we stop.
• If $x^{(i)} + x^{(i+1)}$ is the all-ones vector, then we've bipartitioned the graph; we stop.
• If $x^{(i+1)} = x^{(i-1)}$ (but we're not in the previous case), then we've bipartitioned a connected component; choose an arbitrary $j$ such that $x^{(i)}_j = x^{(i+1)}_j = 0$, set $x^{(i+1)}_j = 1$, and keep going.
• If none of the above hold, just keep going.

Eigenvalue computations, or things like checking for odd cycles by looking for nonzero diagonal entries in $A^3, A^5, A^7, \dots$, are going to be much slower. Also, you can't check for bipartiteness from the degree sequence, because the cube graph (which is bipartite) has the same degree sequence as two disjoint copies of $K_4$ (which are not bipartite).

Answer 2

The following result is helpful.

Let $G$ be a graph and let $A$ be the adjacency matrix of $G$. Then the following conditions are equivalent.

1. $G$ is bipartite.
2. the eigenvalues of $A$ are symmetric with respect to the origin, that is, if $\lambda$ is an eigenvalue of $A$ with multiplicity $k$, then $-\lambda$ is also an eigenvalue of $A$ with multiplicity $k$.