0
$\begingroup$

Given integers $m,n$, I want to compute the maximum possible value of $\Phi(G)$, over all simple, connected, undirected, unweighted graphs $G$ with $n$ vertices and $m$ edges.

The objective function $\Phi$ is defined as follows. Let $v=(v_1,\dots,v_n)$ be the principal eigenvector (PEV) of the adjacency matrix for $G$. Set $x=v/\|v\|_2$, so that $x_1^2 + \dots + x_n^2 = 1$. The define $\Phi(G) = f(x) = x_1^4 + \dots + x_n^4$.

What optimization method can I use to solve this problem? How can I find graph $G$ that makes $\Phi(G)$ as large as possible?

Note that since the graph $G$ is connected, we will have $0 < v_i < 1$ for all $i$. Thus, we are maximizing $f(x)=x_1^4 + \dots + x_n^4$ subject to the constraints that $0 < x_i < 1$, $x_1^2 + \dots + x_n^2 = 1$, and such that $x$ is the $L_2$-normalized principal eigenvector of some simple, connected, undirected, unweighted graph $G$.

I've learned that the constraints $x_1^2+\cdots + x_n^2=1$ and $0 < x_i < 1$ do not form a convex set.

I've tried using simulated annealing for this problem. In each step I pick one edge independently and uniformly at random and remove it and at the same time pick another pair of nodes which don't have an edge and connect them, evaluate how much $\Phi(G)$ changes, and use simulated annealing to decide whether to keep or discard this change. I repeat this iteratively to try to maximize the objective function value. The largest value I could achieve with this process is $0.22$ for a graph with size $n=500$ nodes and $m=2500$ edges. Is there a way to verify whether this solution is optimal or not? Is there a way to verify how far from the optimal solution this is?

$\endgroup$
  • $\begingroup$ What have you tried? Where did you get stuck? Could you be more specific? There are tons of materials, books and ready to use techniques / programs, so have you at least searched before asking? $\endgroup$ – Evil Jul 15 '16 at 23:45
  • 1
    $\begingroup$ I skipped your description of simulated annealing. It seems obvious that your function can get any value $1-\epsilon$ for small $\epsilon$ by choosing all $x_i$ close to $0$ except one that is close to $1$. $\endgroup$ – Hendrik Jan Jul 16 '16 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.