Acceso abierto

Finding Hidden Structures, Hierarchies, and Cores in Networks via Isospectral Reduction

Leonid Bunimovich
Leonid Bunimovich
, 
Dallas Smith
Dallas Smith
 y 
Benjamin Webb
Benjamin Webb
   | 28 jun 2019
Applied Mathematics and Nonlinear Sciences's Cover Image
Acerca de este artículo
Artículo anterior
Artículo siguiente
Cite
Article Category: Papers dedicated to the memory of Valetnin Afraymovich (1945-2018)
Publicado en línea: 28 jun 2019
Páginas: 231 - 254
Recibido: 19 ago 2018
Aceptado: 19 nov 2018
DOI: https://doi.org/10.2478/AMNS.2019.1.00021
Palabras clave
© 2019 Leonid Bunimovich et al., published by Sciendo
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Fig. 1

The network G consisting of six individuals is shown (above) where edge weights indicate the chance that information is passed from one member of the network to one of its neighbors. The reduced network ℛS (G) in which S are the four members {1,2,3,4} is shown (left). By setting λ = ρ(G) = 1 in ℛS (G) the result is the isoradial reduction 𝒫S (G) shown (right). The edges in this reduction represent the probability that information is eventually passed from one member of S to another in the original unreduced network G.
The network G consisting of six individuals is shown (above) where edge weights indicate the chance that information is passed from one member of the network to one of its neighbors. The reduced network ℛS (G) in which S are the four members {1,2,3,4} is shown (left). By setting λ = ρ(G) = 1 in ℛS (G) the result is the isoradial reduction 𝒫S (G) shown (right). The edges in this reduction represent the probability that information is eventually passed from one member of S to another in the original unreduced network G.

Fig. 2

An example of an unweighted, undirected graph G and its corresponding adjacency matrix M (G). The graph has the symmetry given by the automorphism ϕ = (68). The symmetric vertices 6 and 8 are highlighted yellow.
An example of an unweighted, undirected graph G and its corresponding adjacency matrix M (G). The graph has the symmetry given by the automorphism ϕ = (68). The symmetric vertices 6 and 8 are highlighted yellow.

Fig. 3

(Left) The undirected graph G from Figure 2 which has both standard and latent symmetries. Red vertices 2 and 3 are latently symmetric. Yellow vertices 6 and 8 have a standard symmetry between them, but 4 is latently symmetric to both of 6 and 8. (Right) The isospectral reduction of the top graph over vertices 2 and 3, showing the latent symmetry between these two vertices
(Left) The undirected graph G from Figure 2 which has both standard and latent symmetries. Red vertices 2 and 3 are latently symmetric. Yellow vertices 6 and 8 have a standard symmetry between them, but 4 is latently symmetric to both of 6 and 8. (Right) The isospectral reduction of the top graph over vertices 2 and 3, showing the latent symmetry between these two vertices

Fig. 4

(Left) A network representation of the largest strongly connected component of all Wikipedia webpages in the “logic puzzle” category [22]. Vertices represent webpages while the direct edges represent hyperlinks between them. Red vertices are symmetric and the yellow vertex is latently symmetric with the two red vertices. (Right) A Metabolic network of the eukaryotic organism Arabidopsis Thaliana [23]. Latently symmetric vertices are colored red.
(Left) A network representation of the largest strongly connected component of all Wikipedia webpages in the “logic puzzle” category [22]. Vertices represent webpages while the direct edges represent hyperlinks between them. Red vertices are symmetric and the yellow vertex is latently symmetric with the two red vertices. (Right) A Metabolic network of the eukaryotic organism Arabidopsis Thaliana [23]. Latently symmetric vertices are colored red.

Fig. 5

The left figure plots the percentage of graphs which were generated using preferential attachment that contain a standard symmetry. The horizontal axis (plotted logarithmically) gives different values of a, the parameter which controls how strongly each edge is attached preferentially. The right is the same figure in which the occurrences of latent symmetries are plotted.
The left figure plots the percentage of graphs which were generated using preferential attachment that contain a standard symmetry. The horizontal axis (plotted logarithmically) gives different values of a, the parameter which controls how strongly each edge is attached preferentially. The right is the same figure in which the occurrences of latent symmetries are plotted.

Fig. 6

The graph G (left) is isospectrally reduced over the red vertices resulting in the graph Rred(G). The rational function weights f and g are the functions f(x)=x6−6x4+10x4−4x6−6x4+9x2−3  and g(x)=3x6−15x4+18x4−4x(x6−6x4+9x2−3).$f\left( x \right)=\frac{{{x}^{6}}-6{{x}^{4}}+10{{x}^{4}}-4}{{{x}^{6}}-6{{x}^{4}}+9{{x}^{2}}-3}\,\,\text{and }g\left( x \right)=\frac{3{{x}^{6}}-15{{x}^{4}}+18{{x}^{4}}-4}{x\left( {{x}^{6}}-6{{x}^{4}}+9{{x}^{2}}-3 \right)}.$
The graph G (left) is isospectrally reduced over the red vertices resulting in the graph Rred(G). The rational function weights f and g are the functions f(x)=x6−6x4+10x4−4x6−6x4+9x2−3  and g(x)=3x6−15x4+18x4−4x(x6−6x4+9x2−3).$f\left( x \right)=\frac{{{x}^{6}}-6{{x}^{4}}+10{{x}^{4}}-4}{{{x}^{6}}-6{{x}^{4}}+9{{x}^{2}}-3}\,\,\text{and }g\left( x \right)=\frac{3{{x}^{6}}-15{{x}^{4}}+18{{x}^{4}}-4}{x\left( {{x}^{6}}-6{{x}^{4}}+9{{x}^{2}}-3 \right)}.$

Fig. 7

A graphical realization of the DGG network GDGG where there is an edge between Wi and E j if Wi attended E j. Following Freeman and Duquenne [34], yellow and orange vertices represent the first and second set of group events 𝓔1 = {E1–E5} and 𝓔2 = {E10–E14}, respectively. Red vertices represent the joint meetings 𝒥 = {E6–E9}. The blue, purple, and green vertices represent the first, second, and third groups of women 𝒢1 = {W1–W7,W9}, 𝒢2 = {W10–W15,W17,W18}, and 𝒢3 = {W8,W16}, respectively.
A graphical realization of the DGG network GDGG where there is an edge between Wi and E j if Wi attended E j. Following Freeman and Duquenne [34], yellow and orange vertices represent the first and second set of group events 𝓔1 = {E1–E5} and 𝓔2 = {E10–E14}, respectively. Red vertices represent the joint meetings 𝒥 = {E6–E9}. The blue, purple, and green vertices represent the first, second, and third groups of women 𝒢1 = {W1–W7,W9}, 𝒢2 = {W10–W15,W17,W18}, and 𝒢3 = {W8,W16}, respectively.

Fig. 8

The sequence of isospectral reductions G = GDGG,G1,G2, . . . ,G8 of the DGG network using the reduction criterion Γdeg that selects all vertices except those with minimal degree. Edge weights and self-loops are omitted in each reduction as the criterion Γdeg ignores this information.
The sequence of isospectral reductions G = GDGG,G1,G2, . . . ,G8 of the DGG network using the reduction criterion Γdeg that selects all vertices except those with minimal degree. Edge weights and self-loops are omitted in each reduction as the criterion Γdeg ignores this information.

Fig. 9

The graph G and the graph H are spectrally equivalent with respect to the rule L that selects those vertices of a graph that have loops. In particular, the graphs ℛL(G) ≃ ℛL(H) are isomorphic as is shown.
The graph G and the graph H are spectrally equivalent with respect to the rule L that selects those vertices of a graph that have loops. In particular, the graphs ℛL(G) ≃ ℛL(H) are isomorphic as is shown.

The core & periphery membership assignments of the women in the DGG network from 11 different studies are shown above (see the survey [13]). The rankings are from left to right where different core and peripheral levels are separated by in each study and the women are represented by their subscripts. The last four rows show the hierarchy obtained for the first and second groups 𝒢1 = {W1–W7,W9} and 𝒢2 = {W10–W15,W16,W17} using the four reduction criteria Γdeg, Γpage, Γbetw, and Γclose.

Study/Criteria First Group Second Group
DGG 41 1, 2, 3, 4 5, 6, 7 8, 9 13, 14, 15 11, 12 9, 10, 16, 17, 18
HOM 50 1, 2, 3, 4, 5, 6, 7 8 11, 12, 13, 14, 15 8, 17, 18
BCH 78 5 1, 2, 3, 4, 6 14 10, 11, 12, 13, 15
DOR 79 1, 3 2, 4 5, 6, 7, 9 12, 13, 14 10, 11, 15
BCH 91 5 4 2 1, 6 3 7 9 8 17, 18 12 13, 14 11 15 10 16
FW1 93 1, 2, 3, 4 5, 6, 7, 8, 9 16 13, 14, 15 10, 11, 12, 17, 18 16
FW2 93 1 2, 3, 4 5 6 7, 9 14 12, 13, 15 11, 17, 18 10
BE1 97 3, 4 2 1 7 6 9 5 12, 13 11 14 10 15
S&F 99 1, 3 2 4 5 6 7 9 8 12, 13 14 15 11 10 17, 18
ROB 00 1 2 4 3 5 6 7 9 8 12 13 14 11 15 10 16 17 18
NEW 01 1, 2 3 4 6 5 7, 9 13, 14 12 11 15 10 17, 18 8, 16
Γdeg (Degree Centrality) 1, 2, 3, 4 9 5, 6, 7 14 13 12, 15 10, 11 17, 18
CΓpage (Page Rank) 1, 2, 3, 4 9 5 6 7 14 13 12 15 11 10 17, 18
CΓbetw (Betweenness Centrality) 1, 2, 3, 4, 6 5 9 7 14 10, 13, 15 11, 12 17, 18
Γclose (Closeness Centrality) 1, 2, 3, 4, 6 ,7, 9, 5 14 10, 13, 15 11, 12 17, 18
eISSN:
2444-8656
Idioma:
Inglés
Calendario de la edición:
Volume Open
Temas de la revista:
Life Sciences, other, Mathematics, Applied Mathematics, General Mathematics, Physics
RSS Feed de revista