Lets say in Graph $G$ we have two vertices $v$ and $u$, each vertex is connected to several neighbors by edges describing the distances $d_{ij}$ from these neighbors. The neighbors themselves are also connected to more vertices by such edges.

If a vertex has relatively short edges and is connected to neighbors that also have relatively short edges we could say it is in a dense area, the opposite is also true; if a vertex has mostly long edges to neighbors that also have mostly long edges, it's in a relatively sparse area.

I'm looking for a way to measure this sparsity / density and be able to compares this attribute between different vertices.

In essence, we have as input, two lists of scalars (vertexs' edges' lengths) and possibly direct neighbors edges' lengths. We need to output the density measure and be able to compare it between vertices.

What I'm doing now is using a trimmed mean and simply computing the ratio between densities but perhaps there is a more robust approach.

  • $\begingroup$ Is this related to manifold learning or nonlinear dimensionality reduction? $\endgroup$
    – Kirill
    Jul 6 '15 at 1:37

If you want to compute a physical density for a graph then why don't you try and estimate the Number Density. That is, the number of vertices per unit area (or volume if that is more appropriate for your problem).

The problem is what area to use to perform the computation? You may need to sample the local area around a vertex to see how the vertex density behaves as it approaches the vertex. For example,

  1. Select a vertex $u$
  2. Find the distance $d$ to its nearest neighbor
  3. Count the number of vertices $|V_{r}|$ within a radii $r$=$d$, $2d$, $3d$, ..., $Nd$
  4. Compute the density at each radii: $\rho_{d}$, $\rho_{2d}$, $\rho_{3d}$, ..., $\rho_{Nd}$

    $\rho_{r}=|V_{r}| / \pi r^{2}$

  5. Fit a line between the estimates of $\rho$ and the radii $r$: $\rho(r) = m * r + \rho_{0}$

  6. Use the offset $\rho_{0}$ (i.e., $r \rightarrow 0$ ) as your estimate of the density at the vertex $u$.

A few things to keep in mind:

  • You may run into problems of negative density, in which case either this method won't work or you need enforce the constraint $\rho > 0$ during the line fitting optimization.

  • You'll also need to pick a neighborhood size $N$. I would start with $N=10$. That is, start with an order of magnitude from the nearest neighbor.

  • You may also need to verify that a line model is a good local model. You may need to try other functions to get a good prediction.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.