I came across the maximum weight subgraph which is defined as
Let x=(x1, …, xn) in $\{{0, 1}\}^n$ be an indicator vector over nodes of graph G, i.e., node u belongs to S iff $x_u$=1. Then the weight of a subgraph S with K nodes can be expressed as:
$g(S) = \frac{1}{K^2}\sum_{u,v \epsilon S} A(u,v) = x^TAx$
I didn't get the point of dividing it by $K^2$. What's the meaning of that
Again the definition of maximum density subgraph is
The density a subgraph S is given by:
$g(S) = \frac{1}{{|S|}^2}\sum_{u,v\epsilon S} A(u,v) = x^TAx$
However, now $x_u$ = $\frac{1}{|S|}$ if x in S and $x_u$=0 otherwise. The problem of finding a densest subgraph can be relaxed to max
I didn't get this definition as well. What is $|S|$ here and whats the difference with maximum weight subgraph
