|
12
|
|
edited Oct 17 2011 at 22:16 |
Finding a vertex of least distance to all other vertices , in a simple graphusing adjacency matrices
Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, with $A = (A_{ij}) = A^T$ being the $N \times N$ (symmetric) adjacency matrix of $G$, then for $1 \leq k < N$, the $k^{th}$ power $A^k$ has the property that its $(i,j)$ entry $(A^k)_{ij}$ is equal to the number of paths closeness centrality of length $k$ connecting vertices $i$ and $j$ in $G$. For a vertex $i$ its closeness centrality, i$, denoted by $C(i)$, is defined to be the inverse of the mean distance of $i$ to all other vertices of $G$. (Here the distance $d_{ij}=d_{ji}$ between two vertices $i,j$ is simply the number of edges connecting them, orientation being irrelevant.) Formally $C(i) := \frac{N-1}{\sum_{j \neq i}d_{ij}}$. The denominator of $C(i)$ is the sum of all the distances of vertex $i$ to other vertices, and we may call this its peripherality (with respect to the other vertices) in the graph. Clearly, the lower the peripherality of $i$ the higher its closeness centrality $C(i)$, and vice versa.
My question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^*$ of G with
maximum closeness centrality $C(i^*)$, equivalently, minimal peripherality, with average case time complexity and average case space complexity of $\mathcal O(N)$?
For example, let $G$ be the graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where if $T[i] = t_i \neq i$ then there is a (directed) edge going from vertex $i$ to vertex $t_i$. Then such an algorithm $\mathcal A$ , if it exists, should return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$.
There is an obvious matrix-based algorithm for finding $i^*$ that uses $k^{th}$ powers of the adjacency matrix, which encode information about the path lengths of paths that connect two given vertices. But this algorithm, for a graph of $N$ vertices, uses a total of $\mathcal O(N^4)$ steps and uses $\mathcal O(N^2)$ space.
Sincerely, Sandeep Murthy.
|
|
|
|
|
11
|
|
edited Oct 17 2011 at 11:33 |
Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, with $A = (A_{ij}) = A^T$ being the $N \times N$ (symmetric) adjacency matrix of $G$, then for $1 \leq k < N$, the $k^{th}$ power $A^k$ has the property that its $(i,j)$ entry $(A^k)_{ij}$ is equal to the number of paths of length $k$ connecting vertices $i$ and $j$ in $G$. For a vertex $i$ its closeness centrality, denoted by $C(i)$, is defined to be the inverse of the mean distance of $i$ to all other vertices of $G$. (Here the distance $d_{ij}=d_{ji}$ between two vertices $i,j$ is simply the number of edges connecting them, orientation being irrelevant.) Formally $C(i) := \frac{N-1}{\sum_{j \neq i}d_{ij}}$. The denominator of $C(i)$ is the sum of all the distances of vertex $i$ to other vertices, and we may call this its peripherality (with respect to the other vertices) in the graph. Clearly, the lower the peripherality of $i$ the higher its closeness centrality $C(i)$, and vice versa.
My question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^*$ of G with
maximum closeness centrality $C(i^*)$, equivalently, minimal peripherality, with average case time complexity and average case space complexity of $\mathcal O(N)$?
For example, let $G$ be the graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where if $T[i] = t_i \neq i$ then there is a (directed) edge going from vertex $i$ to vertex $t_i$. Then such an algorithm $\mathcal A$ , if it exists, should return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$.
There is an obvious matrix-based algorithm for finding $i^*$ that uses $k^{th}$ powers of the adjacency matrix, which encode information about the path lengths of paths that connect two given vertices. But this algorithm, for a graph of $N$ vertices, uses a total of $\mathcal O(N^4)$ steps and uses $\mathcal O(N^2)$ space.
Sincerely, Sandeep Murthy.
|
|
|
|
|
10
|
|
edited Oct 17 2011 at 11:15 |
My first question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^*$ of G with For example, let $G$ be the graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where if $T[i] = t_i \neq i$ then there is a (directed) edge going from vertex $i$ to vertex $t_i$. Then such an algorithm $\mathcal A$ , if it exists, should return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$. I have a second question about the same kind of graph $G$ as described in the first question, but first an observation. The graph $G$, as described above, is connected (in the weak sense), and will have the property that the $k^{th}$ power $A^k$ of its adjacency matrix $A$ will contain a $1$ in its $(i,j)$ entry if and only if there is a path of length $k$ connecting vertices $i$ and $j$. Since $G$, by definition, is such that any two distinct vertices $i \neq j$ of $G$ are connected by one and only one path of some length $1 \leq d_{ij}=d_{ji} \leq N - 1$, it seems to follow that the distance $d_{ij}$ is equal to some such $k$, i.e. for any distinct vertices $i \neq j$ there is a $1 \leq k \leq N - 1$, such that $(A^k)_{ij} = 1$. My second question is whether the following algorithm, regardless of its efficiency, is functionally correct, i.e. will it produce, in principle, a correct result for every possible valid test input? (I am thinking the input can be given as a zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of integers $0 \leq t_i \leq N-1$ labelling the graph vertices, such that $T[i]=t_i$ is the vertex to which there is a (directed) edge going from vertex $i$, where $i \neq t_i$ . Note that in the graph $G$ I described, if there is an edge or path connecting vertices $i$ and $j$, then one and only such edge or path exists for these vertices.) INPUT: Zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of size $N$ representing the graph $G$, of the kind described above. OUTPUT: An integer $i^*$ labelling a vertex of $G$ with the maximum closeness centrality $C(i^*)$. START: Compute adjacency matrix $A = (A_{ij})$ as $A_{ij}=A_{ji}=1$ if $i \neq T[i]$ and $T[i]=j$, or $A_{ij}=A_{ji}=0$ if either $i=j$ or $T[i] \neq j$.Compute powers $A^k$, for $2 \leq k \leq N - 1$.For all vertex pairs $(i,j)$, where $i < j$, compute distance $d_{ij} = k$, where $1 \leq k \leq N-1$ necessarily exists, such that $(A^k)_{ij} = 1$.For each vertex $i$ of $G$, compute its total distance $T(i) = \sum_{j \neq i}d_{ij}$ to all other vertices.Return a first vertex $i^*$ with the property $T(i^*)$ is a minimum.END Is this algorithm functionally correct? If so, what would be its average case time and space complexity?
|
|
|
|
9
|
|
edited Oct 17 2011 at 0:01 |
Finding a vertex of maximum closeness centrality least distance to all other vertices, in a simple graph using adjacency matrices
Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, with $A = (A_{ij}) = A^T$ being the $N \times N$ (symmetric) adjacency matrix of $G$, then for $1 \leq k < N$, the $k^{th}$ power $A^k$ has the property that its $(i,j)$ entry $(A^k)_{ij}$ is equal to the number of paths of length $k$ connecting vertices $i$ and $j$ in $G$. For a vertex $i$ its closeness centrality, denoted by $C(i)$, is defined to be the inverse of the mean distance of $i$ to all other vertices of $G$. (Here the distance $d_{ij}=d_{ji}$ between two vertices $i,j$ is simply the number of edges connecting them, orientation being irrelevant.) Formally $C(i) := \frac{N-1}{\sum_{j \neq i}d_{ij}}$. The denominator of $C(i)$ is the sum of all the distances of vertex $i$ to other vertices, and we may call this its peripherality (with respect to the other vertices) in the graph. Clearly, the lower the peripherality of $i$ the higher its closeness centrality $C(i)$, and vice versa.
My first question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^*$ of G with
maximum closeness centrality $C(i^*)$, equivalently, minimal peripherality, with average case time complexity and average case space complexity of $\mathcal O(N)$? For example, let $G$ be the graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where if $T[i] = t_i \neq i$ then there is a (directed) edge going from vertex $i$ to vertex $t_i$. Then such an algorithm $\mathcal A$ , if it exists, should return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$.
I have a second question about the same kind of graph $G$ as described in the first question, but first an observation. The graph $G$, as described above, is connected (in the weak sense), and will have the property that the $k^{th}$ power $A^k$ of its adjacency matrix $A$ will contain a $1$ in its $(i,j)$ entry if and only if there is a path of length $k$ connecting vertices $i$ and $j$. Since $G$, by definition, is such that any two distinct vertices $i \neq j$ of $G$ are connected by one and only one path of some length $1 \leq d_{ij}=d_{ji} \leq N - 1$, it seems to follow that the distance $d_{ij}$ is equal to some such $k$, i.e. for any distinct vertices $i \neq j$ there is a $1 \leq k \leq N - 1$, such that $(A^k)_{ij} = 1$.
My second question is whether the following algorithm, regardless of its efficiency, is functionally correct, i.e. will it produce, in principle, a correct result for every possible valid test input? (I am thinking the input can be given as a zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of integers $0 \leq t_i \leq N-1$ labelling the graph vertices, such that $T[i]=t_i$ is the vertex to which there is a (directed) edge going from vertex $i$, where $i \neq t_i$ . Note that in the graph $G$ I described, if there is an edge or path connecting vertices $i$ and $j$, then one and only such edge or path exists for these vertices.)
INPUT: Zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of size $N$ representing the graph $G$, of the kind described above.
OUTPUT: An integer $i^*$ labelling a vertex of $G$ with the maximum closeness centrality $C(i^*)$.
START:
- Compute adjacency matrix
$A = (A_{ij})$ as $A_{ij}=A_{ji}=1$ if $i \neq T[i]$ and $T[i]=j$, or $A_{ij}=A_{ji}=0$ if either $i=j$ or $T[i] \neq j$.
- Compute powers $A^k$, for $2 \leq k \leq N - 1$.
- For all vertex pairs $(i,j)$, where $i < j$, compute distance
$d_{ij} = k$, where $1 \leq k \leq N-1$ necessarily exists, such that $(A^k)_{ij} = 1$.
- For each vertex $i$ of $G$, compute its total distance
$T(i) = \sum_{j \neq i}d_{ij}$ to all other vertices.
- Return a first vertex
$i^*$ with the property $T(i^*)$ is a minimum.
END
Is this algorithm functionally correct? If so, what would be its average case time and space complexity?
Sincerely, Sandeep Murthy.
|
|
|
|
|
8
|
|
edited Oct 16 2011 at 17:24 |
Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, with $A = (A_{ij}) = A^T$ being the $N \times N$ (symmetric) adjacency matrix of $G$, then for $1 \leq k < N$, the $k^{th}$ power $A^k$ has the property that its $(i,j)$ entry $(A^k)_{ij}$ is equal to the number of paths of length $k$ connecting vertices $i$ and $j$ in $G$. For a vertex $i$ its closeness centrality, denoted by $C(i)$, is defined to be the inverse of the mean distance of $i$ to all other vertices of $G$. (Here the distance $d_{ij}=d_{ji}$ between two vertices $i,j$ is simply the number of edges connecting them, orientation being irrelevant.) Formally $C(i) := \frac{N-1}{\sum_{j \neq i}d_{ij}}$. The denominator of $C(i)$ is the sum of all the distances of vertex $i$ to other vertices, and we may call this its peripherality (with respect to the other vertices) in the graph. Clearly, the lower the peripherality of $i$ the higher its closeness centrality $C(i)$, and vice versa.
My first question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^*$ of G with
maximum closeness centrality $C(i^*)$, equivalently, minimal peripherality, with average case time complexity and average case space complexity of $\mathcal O(N)$? For example, let $G$ be the graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where $i \neq T_i$, and if $T[i] = t_i$ is the vertex to which t_i \neq i$ then there is a (directed) edge going from vertex $i$. i$ to vertex $t_i$. Then such an algorithm $\mathcal A$ , if it exists, will should return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$.
I have a second question about the same kind of graph $G$ as described in the first question, but first an observation. The graph $G$, as described above, is connected (in the weak sense), and will have the property that the $k^{th}$ power $A^k$ of its adjacency matrix $A$ will contain a $1$ in its $(i,j)$ entry if and only if there is a path of length $k$ connecting vertices $i$ and $j$. Since $G$, by definition, is such that any two distinct vertices $i \neq j$ of $G$ are connected by one and only one path of some length $1 \leq d_{ij}=d_{ji} \leq N - 1$, it seems to follow that the distance $d_{ij}$ is equal to some such $k$, i.e. for any distinct vertices $i \neq j$ there is a $1 \leq k \leq N - 1$, such that $(A^k)_{ij} = 1$.
My second question is whether the following algorithm, regardless of its efficiency, is functionally correct, i.e. will it produce, in principle, a correct result for every possible valid test input? (I am thinking the input can be given as a zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of integers $0 \leq t_i \leq N-1$ labelling the graph vertices, such that $T[i]=t_i$ is the vertex to which there is a (directed) edge going from vertex $i$, where $i \neq t_i$ . Note that in the graph $G$ I described, if there is an edge or path connecting vertices $i$ and $j$, then one and only such edge or path exists for these vertices.)
INPUT: Zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of size $N$ representing the graph $G$, as of the kind described above.
OUTPUT: An integer $i^*$ labelling a vertex of $G$ with the maximum closeness centrality $C(i^*)$.
START:
- Compute adjacency matrix
$A = (A_{ij})$ as $A_{ij}=A_{ji}=1$ if $i \neq T[i]$ and $T[i]=j$, or $A_{ij}=A_{ji}=0$ if either $i=j$ or $T[i] \neq j$.
- Compute powers $A^k$, for $2 \leq k \leq N - 1$.
- For all vertex pairs $(i,j)$, where $i < j$, compute distance
$d_{ij} = k$, where $1 \leq k \leq N-1$ necessarily exists, such that $(A^k)_{ij} = 1$.
- For each vertex $i$ of $G$, compute its total distance
$T(i) = \sum_{j \neq i}d_{ij}$ to all other vertices.
- Return a first vertex
$i^*$ with the property $T(i^*)$ is a minimum.
END
Is this algorithm functionally correct? If so, what would be its average case time and space complexity?
Sincerely, Sandeep Murthy.
|
|
|
|
|
7
|
|
edited Oct 16 2011 at 16:47 |
|
|
|
|
|
|
6
|
|
edited Oct 16 2011 at 16:05 |
Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, with $A = (A_{ij}) = A^T$ being the $N \times N$ (symmetric) adjacency matrix of $G$, then for $1 \leq k < N$, the $k^{th}$ power $A^k$ has the property that its $(i,j)$ entry $(A^k)_{ij}$ is equal to the number of paths of length $k$ connecting vertices $i$ and $j$ in $G$. For a vertex $i$ its closeness centrality, denoted by $C(i)$, is defined to be the inverse of the mean distance of $i$ to all other vertices of $G$. (Here the distance $d_{ij}=d_{ji}$ between two vertices $i,j$ is simply the number of edges connecting them, orientation being irrelevant.) Formally $C(i) := \frac{N-1}{\sum_{j \neq i}d_{ij}}$. The denominator of $C(i)$ is the sum of all the distances of vertex $i$ to other vertices, and we may call this its peripherality (with respect to the other vertices) in the graph. Clearly, the lower the peripherality of $i$ the higher its closeness centrality $C(i)$, and vice versa.
My first question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^*$ of G with
maximum closeness centrality $C(i^*)$, equivalently, minimal peripherality, with average case time complexity and average case space complexity of $\mathcal O(N)$? For example, let $G$ be the graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where $i \neq T_i$, and $T[i] = t_i$ is the vertex to which there is a (directed) edge going from vertex $i$. Then such an algorithm $\mathcal A$ , if it exists, will return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$.
I have a second question about the same kind of graph $G$ as described in the first question, but first an observation. The graph $G$, as described above, is connected (in the weak sense), and will have the property that the $k^{th}$ power $A^k$ of its adjacency matrix $A$ will contain a $1$ in its $(i,j)$ entry if and only if there is a path of length $k$ connecting vertices $i$ and $j$. Since $G$, by definition, is such that any two distinct vertices $i \neq j$ of $G$ are connected by one and only one path of some length $1 \leq d_{ij}=d_{ji} \leq N - 1$, it seems to follow that the distance $d_{ij}$ is equal to some such $k$, i.e. for any distinct vertices $i \neq j$ there is a $1 \leq k \leq N - 1$, such that $(A^k)_{ij} = 1$.
My second question is whether the following algorithm, regardless of its efficiency, is functionally correct, i.e. will it produce, in principle, a correct result for every possible valid test input? (I am thinking the input can be given as a zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of integers $0 <= \leq t_i <= \leq N-1$ labelling the graph vertices, such that $T[i]=t_i$ is the vertex to which there is a (directed) edge going from vertex $i$, where $i \neq t_i$ . Note that in the graph $G$ I described, if there is an edge or path connecting vertices $i$ and $j$, then one and only such edge or path exists for these vertices.)
INPUT: Zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ representing the graph $G$, as described above.
OUTPUT: An integer $i^*$ labelling a vertex of $G$ with the maximum closeness centrality $C(i^*)$.
START:
- Compute adjacency matrix
$A = (A_{ij})$ as $A_{ij}=A_{ji}=1$ if $i \neq T[i]$ and $T[i]=j$, or $A_{ij}=A_{ji}=0$ if either $i=j$ or $T[i] \neq j$.
- Compute powers $A^k$, for $2 <= \leq k <= \leq N - 1$.
- For all vertex pairs $(i,j)$, where $i < j$, compute distance
$d_{ij} = k$, where $1 <= \leq k <= \leq N-1$ necessarily exists, such that $(A^k)_{ij} = 1$.
- For each vertex $i$ of $G$, compute its total distance
$T(i) = \sum_{j \neq i}d_{ij}$ to all other vertices.
- Return a first vertex
$i^*$ with the property $T(i^*)$ is a minimum.
END
Is this algorithm functionally correct? If so, what would be its average case time and space complexity?
Sincerely, Sandeep Murthy.
|
|
|
|
|
5
|
|
edited Oct 16 2011 at 10:09 |
Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, with $A = (A_{ij}) = A^T$ being the $N \times N$ (symmetric) adjacency matrix of $G$, then for $1 \leq k < N$, the $k^{th}$ power $A^k$ has the property that its $(i,j)$ entry $(A^k)_{ij}$ is equal to the number of paths of length $k$ connecting vertices $i$ and $j$ in $G$. For a vertex $i$ its closeness centrality, denoted by $C(i)$, is defined to be the inverse of the mean distance of $i$ to all other vertices of $G$. (Here the distance $d_{ij}=d_{ji}$ between two vertices $i,j$ is simply the number of edges connecting them, orientation being irrelevant.) Formally $C(i) := \frac{N-1}{\sum_{j \neq i}d_{ij}}$. The denominator of $C(i)$ is the sum of all the distances of vertex $i$ to other vertices, and we may call this its peripherality (with respect to the other vertices) in the graph. Clearly, the lower the peripherality of $i$ the higher its closeness centrality $C(i)$, and vice versa.
My first question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^*$ of G with
maximum closeness centrality $C(i^*)$, equivalently, minimal peripherality, with average case time complexity and average case space complexity of $\mathcal O(N)$? For example, let $G$ is a be the graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where $i \neq T_i$, and $T[i] = t_i$ is the vertex to which there is a (directed) edge going from vertex $i$. Then such an algorithm $\mathcal A$ , if it exists, will return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$.
I have a second question about the same kind of graph $G$ as described in the first question, but first an observation. The graph $G$, as described above, is connected (in the weak sense), and will have the property that the $k^{th}$ power $A^k$ of its adjacency matrix $A$ will contain a $1$ in its $(i,j)$ entry if and only if there is a path of length $k$ connecting vertices $i$ and $j$. Since $G$, by definition, is such that any two distinct vertices $i \neq j$ of $G$ are connected by one and only one path of some length $1 \leq d_{ij}=d_{ji} \leq N - 1$, it seems to follow that the distance $d_{ij}$ is equal to some such $k$, i.e. for any distinct vertices $i \neq j$ there is a $1 \leq k \leq N - 1$, such that $(A^k)_{ij} = 1$.
My second question is whether the following algorithm, regardless of its efficiency, is functionally correct, i.e. will it produce, in principle, a correct result for every possible valid test input? (I am thinking the input can be given as a zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of integers $0 <= t_i <= N-1$ labelling the graph vertices, such that $T[i]=t_i$ is the vertex to which there is a (directed) edge going from vertex $i$, where $i \neq t_i$ . Note that in the graph $G$ I described, if there is an edge or path connecting vertices $i$ and $j$, then one and only such edge or path exists for these vertices.)
INPUT: Zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ representing the graph $G$, as described above.
OUTPUT: An integer $i^*$ labelling a vertex of $G$ with the maximum closeness centrality $C(i^*)$.
START:
- Compute adjacency matrix
$A = (A_{ij})$ as $A_{ij}=A_{ji}=1$ if $i \neq T[i]$ and $T[i]=j$, or $A_{ij}=A_{ji}=0$ if either $i=j$ or $T[i] \neq j$.
- Compute powers $A^k$, for $2 <= k <= N - 1$.
- For all vertex pairs $(i,j)$, where $i < j$, compute distance
$d_{ij} = k$, where $1 <= k <= N-1$ necessarily exists, such that $(A^k)_{ij} = 1$.
- For each vertex $i$ of $G$, compute its total distance
$T(i) = \sum_{j \neq i}d_{ij}$ to all other vertices.
- Return a first vertex
$i^*$ with the property $T(i^*)$ is a minimum.
END
Is this algorithm functionally correct? If so, what would be its average case time and space complexity?
Sincerely, Sandeep Murthy.
|
|
|
|
|
4
|
|
edited Oct 16 2011 at 1:53 |
Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, with $A = (A_{ij}) = A^T$ being the $N \times N$ (symmetric) adjacency matrix of $G$, then I believe there is a result that for $1 \leq k < N$, the $k^{th}$ power $A^k$ has the property that its $(i,j)$ entry $(A^k)_{ij}$ is equal to the number of paths of length $k$ connecting vertices $i$ and $j$ in $G$. Also, there seems to be in the literature a concept of closeness centrality for vertices of a graph: for For a vertex $i$ its closeness centrality, denoted by $C(i)$, is defined to be the inverse of the mean distance of $i$ to all other vertices of $G$. (Here the distance $d_{ij}=d_{ji}$ between two vertices $i,j$ is simply the number of edges connecting them, orientation being irrelevant.) Formally $C(i) := \frac{N-1}{\sum_{j \neq i}d_{ij}}$. The denominator of $C(i)$ is the sum of all the distances of vertex $i$ to other vertices, and we may call this its peripherality (with respect to the other vertices) in the graph. Clearly, the lower the peripherality of $i$ the higher its closeness centrality $C(i)$, and vice versa.
My first question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^*$ of G with
maximum closeness centrality $C(i^*)$, equivalently, minimal peripherality, with average case time complexity and average case space complexity of $\mathcal O(N)$? For example, let $G$ is a graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where $i \neq T_i$, and $T[i] = t_i$ is the vertex to which there is a (directed) edge going from vertex $i$. Then such an algorithm $\mathcal A$ , if it exists, will return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$.
I have a second question about the same kind of graph $G$ as described in the first question, but first an observation. The graph $G$, as described above, is connected (in the weak sense), and will have the property that the $k^{th}$ power $A^k$ of its adjacency matrix $A$ will contain a $1$ in its $(i,j)$ entry if and only if there is a path of length $k$ connecting vertices $i$ and $j$. Since $G$, by definition, is such that any two distinct vertices $i \neq j$ of $G$ are connected by one and only one path of some length $1 \leq d_{ij}=d_{ji} \leq N - 1$, it seems to follow that the distance $d_{ij}$ is equal to some such $k$, i.e. for any distinct vertices $i \neq j$ there is a $1 \leq k \leq N - 1$, such that $(A^k)_{ij} = 1$.
My second question is whether the following algorithm, regardless of its efficiency, is functionally correct, i.e. will it produce, in principle, a correct result for every possible valid test input? (I am thinking the input can be given as a zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of integers $0 <= t_i <= N-1$ labelling the graph vertices, such that $T[i]=t_i$ is the vertex to which there is a (directed) edge going from vertex $i$, where $i \neq t_i$ . Note that in the graph $G$ I described, if there is an edge or path connecting vertices $i$ and $j$, then one and only such edge or path exists for these vertices.)
INPUT: Zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ representing the graph $G$, as described above.
OUTPUT: An integer $i^*$ labelling a vertex of $G$ with the maximum closeness centrality $C(t_i^*)$.C(i^*)$.
START:
- Compute adjacency matrix
$A = (A_{ij})$ as $A_{ij}=A_{ji}=1$ if $i \neq T[i]$ and $T[i]=j$, or $A_{ij}=A_{ji}=0$ if either $i=j$ or $T[i] \neq j$.
- Compute powers $A^k$, for $2 <= k <= N - 1$.
- For all vertex pairs $(i,j)$, where $i < j$, compute distance
$d_{ij} = k$, where $1 <= k <= N-1$ necessarily exists, such that $(A^k)_{ij} = 1$.
- For each vertex $i$ of $G$, compute its total distance
$T(i) = \sum_{j \neq i}d_{ij}$ to all other vertices.
- Return a first vertex
$i^*$ with the property $T(i^*)$ is a minimum.
END
Is this algorithm functionally correct? If so, what would be its average case time and space complexity?
Sincerely, Sandeep Murthy.
|
|
|
|
|
3
|
|
edited Oct 16 2011 at 1:48 |
Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, with $A = (A_{ij}) = A^T$ being the $N \times N$ (symmetric) adjacency matrix of $G$, then I believe there is a result that for $1 \leq k < N$, the $k^{th}$ power $A^k$ has the property that its $(i,j)$ entry $(A^k)_{ij}$ is equal to the number of paths of length $k$ connecting vertices $i$ and $j$ in $G$. Also, there seems to be in the literature a concept of closeness centrality for vertices of a graph: here for a vertex $i$ its closeness centrality, denoted by $C(i)$, is defined to be the inverse of the mean distance of $i$ to all other vertices of $G$. (Here the distance $d_{ij}=d_{ji}$ between two vertices $i,j$ is simply the number of edges connecting them, orientation being irrelevant.) Formally $C(i) := \frac{N-1}{\sum_{j \neq i}d_{ij}}$.
My first question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^*$ of G with
maximum closeness centrality $C(i^*)$, with average case time complexity and average case space complexity of $\mathcal O(N)$? For example, let $G$ is a graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where $i \neq T_i$, and $T[i] = t_i$ is the vertex to which there is a (directed) edge going from vertex $i$. Then such an algorithm $\mathcal A$ , if it exists, will return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$.
I have a second question about the same kind of graph $G$ as described in the first question, but first an observation. The graph $G$, as described above, is connected (in the weak sense), and will have the property that the $k^{th}$ power $A^k$ of its adjacency matrix $A$ will contain a $1$ in its $(i,j)$ entry if and only if there is a path of length $k$ connecting vertices $i$ and $j$. Since $G$, by definition, is such that any two distinct vertices $i \neq j$ of $G$ are connected by one and only one path of some length $1 \leq d_{ij}=d_{ji} \leq N - 1$, it seems to follow that the distance $d_{ij}$ is equal to some such $k$, i.e. for any distinct vertices $i \neq j$ there is a $1 \leq k \leq N - 1$, such that $(A^k)_{ij} = 1$.
My second question is whether the following algorithm, regardless of its efficiency, is functionally correct, i.e. will it produce, in principle, a correct result for every possible valid test input? (I am thinking the input can be given as a zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of integers $0 <= t_i <= N-1$ labelling the graph vertices, such that $T[i]=t_i$ is the vertex to which there is a (directed) edge going from vertex $i$, where $i \neq t_i$ . Note that in the graph $G$ I described, if there is an edge or path connecting vertices $i$ and $j$, then one and only such edge or path exists for these vertices.)
INPUT: Zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ representing the graph $G$, as described above.
OUTPUT: An integer $i^*$ labelling a vertex of $G$ with the maximum closeness centrality $C(t_i^*)$.
START:
- Compute adjacency matrix
$A = (A_{ij})$ as $A_{ij}=A_{ji}=1$ if $i \neq T[i]$ and $T[i]=j$, or $A_{ij}=A_{ji}=0$ if either $i=j$ or $T[i] \neq j$.
- Compute powers $A^k$, for $2 <= k <= N - 1$.
- For all vertex pairs $(i,j)$, where $i < j$, compute distance
$d_{ij} = k$, where $1 <= k <= N-1$ necessarily exists, such that $(A^k)_{ij} = 1$.
- For each vertex $i$ of $G$, compute its total distance
$T(i) = \sum_{j \neq i}d_{ij}$ to all other vertices.
- Return a first vertex
$i^*$ with the property $T(i^*)$ is a minimum.
END
Is this algorithm functionally correct? If so, what would be its average case time and space complexity?
Sincerely, Sandeep Murthy.
|
|
|
|
|
2
|
|
edited Oct 16 2011 at 1:42 |
Calculating Finding a vertex of maximum closeness centrality in a simple graph using adjacency matrices
Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, with $A = (A_{ij}) = A^T$ being the $N \times N$ (symmetric) adjacency matrix of $G$, then I believe there is a result that for $1 <= \leq k < N$, the $k^{th}$ power $A^k$ has the property that its $(i,j)$ entry $(A^k)_{ij}$ is equal to the number of paths of length $k$ connecting vertices $i$ and $j$ in $G$. Also, there seems to be in the literature a concept of closeness centrality for vertices of a graph: here for a vertex $i$ its closeness centrality, denoted by $C(i)$, is defined to be the inverse of the mean distance of $i$ to all other vertices of $G$. (Here the distance $d_{ij}=d_{ji}$ between two vertices $i,j$ is simply the number of edges connecting them, orientation being irrelevant.) Formally $C(i) := \frac{N-1}{\sum_{j \neq i}d_{ij}}$.
My first question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^*$ of G with
maximum closeness centrality $C(i^*)$, with average case time complexity and average case space complexity of $\mathcal O(N)$? For example, let $G$ is a graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where $i \neq T_i$, and $T[i] = t_i$ is the vertex to which there is a (directed) edge going from vertex $i$. Then such an algorithm $\mathcal A$ , if it exists, will return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$.
I have a second question about the same kind of graph $G$ as described in the first question, but first an observation. The graph $G$, as described above, is connected (in the weak sense), and will have the property that the $k^{th}$ power $A^k$ of its adjacency matrix $A$ will contain a $1$ in its $(i,j)$ entry if and only if there is a path of length $k$ connecting vertices $i$ and $j$. Since $G$, by definition, is such that any two distinct vertices $i \neq j$ of $G$ are connected by one and only one path of some length $1 <= \leq d_{ij}=d_{ji} <= \leq N - 1$, it seems to follow that the distance $d_{ij}$ is equal to some such $k$, i.e. for any distinct vertices $i \neq j$ there is a $1 <= \leq k <= \leq N - 1$, such that $(A^k)_{ij} = 1$.
My second question is whether the following algorithm, regardless of its efficiency, is functionally correct, i.e. will it produce, in principle, a correct result for every possible valid test input? (I am thinking the input can be given as a zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of integers $0 <= t_i <= N-1$ labelling the graph vertices, such that $T[i]=t_i$ is the vertex to which there is a (directed) edge going from vertex $i$, where $i \neq t_i$ . Note that in the graph $G$ I described, if there is an edge or path connecting vertices $i$ and $j$, then one and only such edge or path exists for these vertices.)
INPUT: Zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ representing the graph $G$, as described above.
OUTPUT: An integer $i^*$ labelling a vertex of $G$ with the maximum closeness centrality $C(t_i^*)$.
START:
- Compute adjacency matrix `$A
$A = (A_{ij})$` A_{ij})$ as `$A_{ij}=A_{ji}=1$` $A_{ij}=A_{ji}=1$ if $i \neq T[i]$ and $T[i]=j$, or `$A_{ij}=A_{ji}=0$` $A_{ij}=A_{ji}=0$ if either $i=j$ or $T[i] \neq j$.
- Compute powers $A^k$, for $2 <= k <= N - 1$.
- For all vertex pairs $(i,j)$, where $i
<p> compute < j$, compute distance `$d_{ij} $d_{ij} = k$`k$, where $1 <= k <= N-1$ necessarily exists, such that $(A^k)_{ij} = 1$.</p>
<p> For
- For each vertex $i$ of $G$:</p>
<p> compute G$, compute its total distance `$T(i)
$T(i) = \sum_{j \neq i}d_{ij}$` i}d_{ij}$ to all other vertices.</p>
<p> Return
- Return a first vertex `$i^*$`
$i^*$ with the property that $T(i^*)$ is a minimumwith respect to all $T(i)$ of vertices $i$.</p>
.
END
Is this algorithm functionally correct? If so, what would be its average case time and space complexity?
Sincerely, Sandeep Murthy.
|
|
|
|
|
1
|
|
asked Oct 16 2011 at 1:29 |
Calculating a vertex of maximum closeness centrality in a simple graph using adjacency matrices
Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, with $A = (A_{ij}) = A^T$ being the $N \times N$ (symmetric) adjacency matrix of $G$, then I believe there is a result that for $1 <= k < N$, the $k^{th}$ power $A^k$ has the property that its $(i,j)$ entry $(A^k)_{ij}$ is equal to the number of paths connecting vertices $i$ and $j$ in $G$. Also, there seems to be in the literature a concept of closeness centrality for vertices of a graph: here for a vertex $i$ its closeness centrality, denoted by $C(i)$, is defined to be the inverse of the mean distance of $i$ to all other vertices of $G$. (Here the distance $d_{ij}=d_{ji}$ between two vertices $i,j$ is simply the number of edges connecting them, orientation being irrelevant.) Formally $C(i) := \frac{N-1}{\sum_{j \neq i}d_{ij}}$.
My first question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^*$ of G with
maximum closeness centrality $C(i^*)$, with average case time complexity and average case space complexity of $\mathcal O(N)$? For example, let $G$ is a graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where $i \neq T_i$, and $T[i] = t_i$ is the vertex to which there is a (directed) edge going from vertex $i$. Then such an algorithm $\mathcal A$ , if it exists, will return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$.
I have a second question about the same kind of graph $G$ as described in the first question, but first an observation. The graph $G$, as described above, is connected (in the weak sense), and will have the property that the $k^{th}$ power $A^k$ of its adjacency matrix $A$ will contain a $1$ in its $(i,j)$ entry if and only if there is a path of length $k$ connecting vertices $i$ and $j$. Since $G$, by definition, is such that any two distinct vertices $i \neq j$ of $G$ are connected by one and only one path of some length $1 <= d_{ij}=d_{ji} <= N - 1$, it seems to follow that the distance $d_{ij}$ is equal to some such $k$, i.e. for any distinct vertices $i \neq j$ there is a $1 <= k <= N - 1$, such that $(A^k)_{ij} = 1$.
My second question is whether the following algorithm, regardless of its efficiency, is functionally correct, i.e. will it produce, in principle, a correct result for every possible valid test input? (I am thinking the input can be given as a zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of integers $0 <= t_i <= N-1$ labelling the graph vertices, such that $T[i]=t_i$ is the vertex to which there is a (directed) edge going from vertex $i$, where $i \neq t_i$ . Note that in the graph $G$ I described, if there is an edge or path connecting vertices $i$ and $j$, then one and only such edge or path exists for these vertices.)
INPUT: Zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ representing the graph $G$, as described above.
OUTPUT: An integer $i^*$ labelling a vertex of $G$ with the maximum closeness centrality $C(t_i^*)$.
START:
Compute adjacency matrix `$A = (A_{ij})$` as `$A_{ij}=A_{ji}=1$` if $i \neq T[i]$ and $T[i]=j$, or `$A_{ij}=A_{ji}=0$` if either $i=j$ or $T[i] \neq j$.
Compute powers $A^k$, for $2
For all vertex pairs $(i,j)$, where $i
<p> compute distance `$d_{ij} = k$`, where $1 <= k <= N-1$ necessarily exists, such that $(A^k)_{ij} = 1$.</p>
<p> For each vertex $i$ of $G$:</p>
<p> compute its total distance `$T(i) = \sum_{j \neq i}d_{ij}$` to all other vertices.</p>
<p> Return a first vertex `$i^*$` with the property that $T(i^*)$ is a minimum with respect to all $T(i)$ of vertices $i$.</p>
END
Is this algorithm functionally correct? If so, what would be its average case time and space complexity?
Sincerely, Sandeep Murthy.
|
|
|
