Intuition behind the Charikar's LP formulation for densest subgraph problem I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper. 
Just mentioning the LP for maximum density of a subgraph of G(V,E)

$$ \max{\sum_{(i,j) \in E} {x_{ij}}}$$
$$\text{s.t.}$$
$$\forall (i,j)\in E \quad x_{ij} \leq y_i$$
$$\forall (i,j)\in E \quad x_{ij} \leq y_j$$
$$\sum_{i \in V}y_i \leq 1$$
$$\forall (i,j)\in E, i \in V \quad x_{ij}, y_i \geq 0$$
Depending on how people interpret "research-level", this might need to be moved to cs.stackexchange.com.

The intuition becomes more apparent if you first write down an alternate similar looking but not necessarily linear mathematical program

$$\begin{eqnarray}
\textrm{maximize}\,\,&amp;\tfrac{\sum_{(i,j) \in E} x_{ij}}{\sum_{i \in V} y_i}&amp; \\
\textrm{subject to}\,\,&amp; x_{ij} \leq y_i&amp; \forall {(i,j) \in E}\\
&amp; x_{ij} \leq y_j&amp; \forall {(i,j) \in E} \\
&amp; 0 \leq x_{ij} \leq 1 &amp;\forall {(i,j) \in E} \\
&amp; 0 \leq y_i \leq 1 &amp;\forall {i \in V} \\
\end{eqnarray}$$

Integer solutions to this program have a simple interpretation, with $y_i = 1$ iff vertex $i$ is in a chosen subgraph, $x_{ij} = 1$ only if $(i,j)$ is an edge in the subgraph induced by the selected vertices, and the objective function coming directly from the definition of the densest subgraph. Unfortunately, the objective function as written is not valid for an LP. 

The key observation is that the objective function is scale-free, in that dividing all $x_{ij}s$ and $y_i$s of a feasible solution by the same constant value $k \geq 1$ does not affect either feasibility of a solution or its corresponding objective function value. Hence, we can without loss of generality restrict our attention to the case that $\sum_{i \in V} y_i = 1$ (otherwise, we can divide all LP variables by exactly $k=\sum_{i \in V} y_i$ to ensure this). We make this restriction explicit by adding in the constraint $\sum_{i \in V} y_i = 1$. But, with this constraint in hand, the denominator of the objective function for the above program is exactly $1$. Hence, we can remove it from the objective, leaving us with something that is linear, and in particular with the LP in the original post.