Degree of proximity (graph theory)

The degree of proximity of the node (to other nodes) is a measure of centrality in the network, calculated as the reciprocal of the sum of the lengths of the shortest paths between the node and all other nodes of the graph. Thus, the more central the node, the closer it is to all other nodes.

Content

1 Definition
2 In disconnected graphs
3 Options
4 See also
5 notes
6 Literature

Definition

In 1950, Bavelas defined the degree of proximity as the reciprocal of the distance ^[1] ^[2] , that is

C(x)={\frac {1}{\sum _{y}d(y,x)}}.

{\ displaystyle C (x) = {\ frac {1} {\ sum _ {y} d (y, x)}}.}

Where $d(y,x)$ ${\ displaystyle d (y, x)}$ equal to the distance between the vertices $x$ ${\ displaystyle x}$ and $y$ ${\ displaystyle y}$ . When talking about the degree of proximity, usually it is meant its normalized form, which represents the average shortest paths instead of their sum. It is usually given by the previous formula times $N-1$ ${\ displaystyle N-1}$ where $N$ ${\ displaystyle N}$ equal to the number of nodes in the graph. For large graphs, this difference becomes insignificant, so $-1$ ${\ displaystyle -1}$ falls:

C(x)={\frac {N}{\sum _{y}d(y,x)}}.

{\ displaystyle C (x) = {\ frac {N} {\ sum _ {y} d (y, x)}}.}

This correction allows comparisons between nodes of graphs of different sizes.

Considering distances from or to other nodes does not make sense for undirected graphs, while it can give completely different results for oriented graphs (for example, a website may have a high degree of proximity for an outgoing connection, but a low degree of proximity for incoming connections) .

In disconnected graphs

If the graph is not strongly connected , the idea of using the sum of reciprocal quantities to distances instead of the reciprocal to the sum of distances is widespread with the agreement that $1/\infty =0$ ${\ displaystyle 1 / \ infty = 0}$ :

H(x)=\sum _{y\neq x}{\frac {1}{d(y,x)}}.

{\ displaystyle H (x) = \ sum _ {y \ neq x} {\ frac {1} {d (y, x)}}.}

The most natural modification of Bavelas’s definition of proximity is the following general principle, proposed by Marchioni and Lator (2000) ^[3] , that in graphs with unlimited distances the harmonic mean behaves better than the arithmetic mean. Moreover, the proximity of Bavelos can be described as an abnormalized inverse of the arithmetic mean distance, while harmonic centrality is equal to the abnormalized value inverse to the mean harmonic distance.

This idea was clearly expressed for oriented graphs by Dekker under the name of significant centrality ( English valued centrality ) ^[4] and Roach under the name of harmonic centrality (2009) ^[5] . Garg axiomatized the concept (2009) ^[6] , and Opsal proposed it again (2010) ^[7] . The concept was studied on oriented general graphs of Boldi and Vigna (2014) ^[8] . This idea is very similar to the marketing potential proposed by Harris (1954) ^[9] , which is now often used under the name market access ^[10] .

Options

Dangalchev (2006) ^[11] in his work on the vulnerability of networks proposed a different definition for undirected graphs:

D(x)=\sum _{y\neq x}{\frac {1}{2^{d(y,x)}}}.

{\ displaystyle D (x) = \ sum _ {y \ neq x} {\ frac {1} {2 ^ {d (y, x)}}}.}

This definition is used effectively for unrelated graphs and allows a convenient formulation of graph operations. For example:

If the graph $G_{1}+G_{2}$ ${\ displaystyle G_ {1} + G_ {2}}$ created by connecting a node $p$ ${\ displaystyle p}$ count $G_{1}$ ${\ displaystyle G_ {1}}$ with a knot $q$ ${\ displaystyle q}$ count $G_{2}$ ${\ displaystyle G_ {2}}$ , then the degree of proximity of the combined graph is equal to:

D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+(1+D(p))(1+D(q)).

{\ displaystyle D (G_ {1} + G_ {2}) = D (G_ {1}) + D (G_ {2}) + (1 + D (p)) (1 + D (q)).}

If the graph $T(G)$ ${\ displaystyle T (G)}$ is a thorn graph ( eng. thorn graph ^[12] ) $G$ ${\ displaystyle G}$ having $n$ ${\ displaystyle n}$ nodes, then the degree of proximity $T(G)$ ${\ displaystyle T (G)}$ equal to ^[13] :

D(T(G))={\frac {9}{4}}D(G)+n.

{\ displaystyle D (T (G)) = {\ frac {9} {4}} D (G) + n.}

A natural generalization of the definition ^[14] :

D(x)=\sum _{y\neq x}\ {\alpha ^{d(y,x)}},

{\ displaystyle D (x) = \ sum _ {y \ neq x} \ {\ alpha ^ {d (y, x)}},}

Where $\alpha$ ${\ displaystyle \ alpha}$ belongs to the interval (0,1). With increasing $\alpha$ ${\ displaystyle \ alpha}$ from 0 to 1, the generalized degree of proximity changes from a local characteristic (degree of apex) to global (the number of connected nodes).

The informational centrality of Stephenson and Zelen (1989) is another measure of proximity that calculates the harmonic mean of the resistance distances in the direction of the vertex x , which is smaller if x has many paths with low resistance connecting it to other vertices ^[15] .

In the classical definition of the degree of proximity, the dissemination of information is modeled using the shortest paths. This model may not be entirely realistic for some types of communication scenarios. Related definitions of proximity measures were discussed, such as the proposed by Noh and Rieger (2004). This indicator measures the speed with which random message routes reach the top from anywhere in the graph - a variant of the degree of proximity based on random walks ^[16] . Tran and Kwon (2014) ^[17] is an extended measure of the degree of proximity based on another approach to circumvent restrictions on the degree of proximity for graphs that do not have strong connectivity. Hierarchical centrality explicitly includes information about the set of other nodes that this node can affect.

Notes

↑ Bavelas, 1950 , p. 725-730.
↑ Sabidussi, 1966 , p. 581-603.
↑ Marchiori, Latora, 2000 , p. 539-546.
↑ Dekker, 2005 .
↑ Rochat, 2009 .
↑ Garg, 2009 .
↑ Opsahl, 2010 .
↑ Boldi, Vigna, 2014 , p. 222–262.
↑ Harris, 1954 , p. 315–348.
↑ Gutberlet, 2014 .
↑ Dangalchev, 2006 , p. 556.
↑ A bar graph of a graph G is a graph obtained by adding to each node of the graph G a certain number of additional hanging vertices, that is, vertices associated only with this node ( Azari 2018 ).
↑ Dangalchev, 2018 , p. 1-15.
↑ Dangalchev, 2011 , p. 1939-1948.
↑ Stephenson, Zelen, 1989 , p. 1–37.
↑ Noh, Rieger, 2004 , p. 118701.
↑ Tran, Kwon, 2014 .

Literature

Mahdieh Azari. ON THE GUTMAN INDEX OF THORN GRAPHS // Kragujevac J. Sci .. - 2018 .-- T. 40 . - S. 33-48 .
Chavdar Dangalchev. Residual Closeness in Networks // Physica A. - 2006 .-- T. 365 .
Chavdar Dangalchev. Residual Closeness of Generalized Thorn Graphs // Fundamenta Informaticae. - 2018 .-- T. 162 , no. 1 .
Chavdar Dangalchev. Residual Closeness and Generalized Closeness // IJFCS. - 2011 .-- T. 22 , no. 8 .
Massimo Marchiori, Vito Latora. Harmony in the small-world // Physica A: Statistical Mechanics and its Applications. - 2000. - T. 285 , no. 3-4 . - DOI : 10.1016 / s0378-4371 (00) 00311-3 . - . - arXiv : cond-mat / 0008357 .
Anthony Dekker. Conceptual Distance in Social Network Analysis // Journal of Social Structure. - 2005. - T. 6 , no. 3 .
Yannick Rochat. Closeness centrality extended to unconnected graphs: The harmonic centrality index // Applications of Social Network Analysis, ASNA 2009 . - 2009.
Manuj Garg. Axiomatic Foundations of Centrality in Networks. - 2009. - DOI : 10.2139 / ssrn.1372441 .
Tore Opsahl. Closeness centrality in networks with disconnected components . - 2010. - March.
Paolo Boldi, Sebastiano Vigna. Axioms for Centrality // Internet Mathematics. - 2014 .-- T. 10 , no. 3-4 . - DOI : 10.1080 / 15427951.2013.865686 .
Harris CD The, market as a factor in the localization of industry in the united states // Annals of the association of American geographers. - 1954. - T. 44 , no. 4 .
Theresa Gutberlet. Cheap Coal versus Market Access: The Role of Natural Resources and Demand in Germany's Industrialization // Working Paper. - 2014.
Alex Bavelas. Communication patterns in task-oriented groups // J. Acoust. Soc. Am. - 1950.- T. 22 , no. 6 .
Sabidussi G. The centrality index of a graph // Psychometrika. - 1966. - T. 31 , no. 4 . - DOI : 10.1007 / bf02289527 . - PMID 5232444 .
Stephenson KA, Zelen M. Rethinking centrality: Methods and examples // Social Networks. - 1989.- T. 11 . - DOI : 10.1016 / 0378-8733 (89) 90016-6 .
Noh JD, Rieger H. Random Walks on Complex Networks // Phys. Rev. Lett .. - 2004 .-- T. 92 , no. 11 . - DOI : 10.1103 / physrevlett . 92.118701 . - . - arXiv : cond-mat / 0307719 . - PMID 15089179 .
Tien-Dzung Tran, Yung-Keun Kwon. Hierarchical closeness efficiently predicts disease genes in a directed signaling network // Computational biology and chemistry. - 2014. - September ( t. 53PB ). - ISSN 1476-928X .

[_04f071204d94fcbf-1] Bavelas, 1950 , p. 725-730.

[_7f4ff1eae0cf3318-2] Sabidussi, 1966 , p. 581-603.

[_035edd2bbf0443fd-3] Marchiori, Latora, 2000 , p. 539-546.

[_6e07d09648e11ef0-4] Dekker, 2005 .

[_b1d5152a26181adf-5] Rochat, 2009 .

[_7c0e13312164e1cd-6] Garg, 2009 .

[_1d4c7601f98635a7-7] Opsahl, 2010 .

[_029aec085c3bce0c-8] Boldi, Vigna, 2014 , p. 222–262.

[_caff0542ee54fadc-9] Harris, 1954 , p. 315–348.

[_55ba5bcfca1e0ad4-10] Gutberlet, 2014 .

[_7e553d06f94aea9c-11] Dangalchev, 2006 , p. 556.

[12] A bar graph of a graph G is a graph obtained by adding to each node of the graph G a certain number of additional hanging vertices, that is, vertices associated only with this node ( Azari 2018 ).

[_7d8eb5da3c845091-13] Dangalchev, 2018 , p. 1-15.

[_1410f34c54346df1-14] Dangalchev, 2011 , p. 1939-1948.

[_b68622c413a0f84d-15] Stephenson, Zelen, 1989 , p. 1–37.

[_702a03d3d886e28e-16] Noh, Rieger, 2004 , p. 118701.

[_0b8a80d8b29dd92a-17] Tran, Kwon, 2014 .