Questions tagged [graph-distance]
The graph-distance tag has no summary.
21 questions
2 votes
0 answers
337 views
Chess pieces metrics in higher dimensions
A couple of days ago, I was thinking about applying the knight (the well-known piece of chess) metric to any cubic lattice $\mathbb{N}^k$, $k \in \mathbb{N}-\{0,1\}$. I suddenly realized that, from $k ...
- 1,905
1 vote
0 answers
243 views
What is a good algorithm to measure similarity between isomorphic graphs with different node labels?
I am using graphs to represent some structured data. In my case, I have a time series of undirected unweighted graphs with the same topology (i.e. isomorphic graphs with same number of nodes and edges,...
- 163
1 vote
1 answer
150 views
Does exponential degree distribution entail Log-normal distance distribution in large complex graphs?
We've been exploring the graph structure of a large genealogical data base (WikiTree) of which main connected component contains about 23 million nodes. The graph edges are defined by any direct ...
1 vote
0 answers
218 views
Finding a tree with adjacency matrix near a given matrix
For defining a distance between trees, one can code them into $\mathbb{R}^n$ and use norms in $\mathbb{R}^n$ as distance. (For example we can use adjacency matrices as a tool for this coding) After ...
- 119
0 votes
1 answer
221 views
"Arc" length parametrization for surfaces
If we have a function $\phi:\Omega\subseteq\mathbb{R}^2\to\mathbb{R}$, $\phi\in C^2(\Omega)$ is there a way to find a function $d:\Omega\to\mathbb{R}, d\in C^2(\Omega)$ so that: $|\nabla d(x,y)|=1,\ \...
- 2,029
2 votes
0 answers
90 views
Antipodal vertices in spectral graph embeddings
Suppose your are given an antipodal graph $G=(V,E)$, that is, for every vertex $v\in V$ there is a unique maximally distant vertex $v'\in V$. Under which condistions does the following hold: If $\...
- 14.5k
1 vote
1 answer
241 views
Distance pairs in labeled directed graph
Suppose we have a simple directed graph with $n$ nodes and $m$ edges, and we label each edge from $1$ to $m$ (with distinct labels). Define the weighted "length" of a directed path to be the maximum ...
- 130
3 votes
1 answer
239 views
Voronoi diagram on (weighted) graphs
Suppose I have a graph $G$ (possibly with weights on edges), and I have a subset $S$ of $k$ vertices $s_1, \dotsc, s_k$. I want to solve the post office problem: that is, I want to partition the ...
0 votes
1 answer
431 views
Distance function and its approximation
An easy and quick question: Consider a function $u\in C(\Omega)$, where $\Omega$ is a bounded domain in $\mathbb{R}^n$. Define a function $Q$ that measures the distance of a point $(x,y) \in\mathbb{...
- 59
2 votes
1 answer
157 views
Distance between two polyhedra that takes incidence structure into account
Suppose that we have two polyhedra $P_1$ and $P_2$ in $\mathbb{R}^3$. I would like to define such a metric $\rho(P_1, P_2)$ that depends on several factors, but currently I don't know how to do it ...
- 123
4 votes
0 answers
551 views
Graph contained in a metric space
I have a metric space $X$ and a graph $G=(V,E)$ whose set of vertices is a subset $V\subset X$ (and $E$ is the set of edges, which is a symmetric subset of $V\times V$). For each $v\in V$, the set of ...
- 7,916
3 votes
1 answer
2k views
Finding the farthest point from a set of other points
I have a set of nodes in a very large graph which I call Cluster Points. I also have for each point in the graph, the distance from each point in the Cluster point set. For example: ...
- 133
0 votes
1 answer
4k views
Is the Haversine Formula or the Vincenty's Formula better for calculating distance?
Which is better for calculating the distance between two latitude/longitude points, The Haversine Formula or The Vincenty's Formula? Why? The distance is obviously being calculated on Earth. Does ...
- 119
5 votes
0 answers
383 views
Edit distance vs. canonical adjacency matrix distance
Let $G$ and $G'$ be two simple random graphs on the same set of nodes. Let $d_{edit}$ be the edit distance between $G$ and $G'$. Let $\mathbf{A}$ and $\mathbf{A'}$ be the adjacency matrices of the ...
- 83
1 vote
0 answers
185 views
Of the standard distance metrics, which ones can/cannot be embedded in Euclidean space?
Given the discussion from: Representability of finite metric spaces it appears that a 1974 paper by Morgan gives the criteria for when a distance metric can be embedded in Euclidean space. My first ...
- 11
1 vote
0 answers
3k views
Possible ways to create a graph representation from a distance matrix (through approximation)
Forgive me, Im not math professional, but a computer scientist at the beginning of my base research from my thesis, so bare with me if I miss something blatantly obvious. I have a Euclidean distance ...
- 111
2 votes
0 answers
87 views
Looking for similar centrality measurement on graph
I'm working on a graph problem somehow related to centrality measurement. Given an undirected, unweighted tree $T$ and a vertex $v$, let $D_i(v)$ be the set of vertices in $T$ that are i hops from $v$,...
- 21
1 vote
1 answer
238 views
planar bipartite cubic graph
Suppose we have a cubic planar bipartite graph with no double edges. I am looking for a statement about the minimal distance between the square faces (shortest path from a vertex on the first square ...
- 31
8 votes
3 answers
3k views
Distance between two networks
Suppose you have networks A and B, each with a set of nodes and edges. You want to measure how similar the networks are to each-other. None of the nodes or edges are labelled. What are the metric(s) ...
- 181
0 votes
1 answer
371 views
Graphs with circulant distance matrices
The cycle has this property. For instance, the distance matrix for a 6-cycle is: $A=\begin{bmatrix} 0 & 1 & 2 & 3 & 2 & 1 \\\\ 1 & 0 & 1 &...
- 7,082
3 votes
2 answers
500 views
Graphs with a unique transmission value
If $G$ is a graph with distance function $d(x,y)$ between vertices, the transmission of a vertex $x \in v(G)$ is defined as $\sigma_{x}=\sum_{y \neq x}{d(x,y)}$. I want to know if there is a known ...
- 7,082