Graph gallery: further examples

For a new graph-distance embedding, start with SGD metric MDS and use sparse mode when full fitting is too costly. The weighted-GRIP and edge-KK examples here document alternatives or saved comparisons; they are not an automatic large-graph pipeline.

This companion contains the other nine graphs from the same saved gallery. See the main gallery for the method, errors, alignment, conversion rules, and complete reproduction recipe. All vertices and edges remain in every display; the examples are split across pages to reduce the number of simultaneous 3D views.

#> Warning in in_dir(input_dir(), expr): You changed the working directory to
#> /tmp/RtmpovXjjF/Rbuild279a46351567/grip/vignettes (probably via setwd()). It
#> will be restored to /tmp/RtmpovXjjF/Rinst279a1a19fb33/grip/scripts. See the
#> Note section in ?knitr::knit

Graphs from applications

dwt_307: a structural graph

A structural graph included among the paper’s examples. It provides a useful contrast to the other meshes.

307 vertices; 1108 edges. Unit edge lengths.

g <- suitesparse.graph('dwt_307')

Source and metadata.

Layout	Graph-distance error	Edge-length error	Stage seconds
Metric MDS	0.1095	0.3558	1.314
MDS + edge-KK	0.3186	0.0780	0.010

494_bus: a power network

The connectivity of a 494-bus power-system matrix. Electrical values are preserved in the source file but are not layout distances.

494 vertices; 586 edges. Unit edge lengths.

g <- suitesparse.graph('494_bus')

Source and metadata.

Layout	Graph-distance error	Edge-length error	Stage seconds
Metric MDS	0.1377	0.5812	3.446
MDS + edge-KK	0.1758	0.1229	0.009

Les Miserables

Characters in Les Miserables are connected when they appear in the same chapter. Character names are retained in vertex_data.

77 vertices; 254 edges. Unit edge lengths.

g <- suitesparse.graph('lesmis')

Source and metadata.

Layout	Graph-distance error	Edge-length error	Stage seconds
Metric MDS	0.1744	0.4114	0.084
MDS + edge-KK	0.2938	0.1777	0.004

dwt_66: a small structural graph

A small structural graph from the Harwell–Boeing collection. Its elongated structure makes bends and twists easy to inspect.

66 vertices; 127 edges. Unit edge lengths.

g <- suitesparse.graph('dwt_66')

Source and metadata.

Layout	Graph-distance error	Edge-length error	Stage seconds
Metric MDS	0.0119	0.2956	0.063
MDS + edge-KK	0.0236	0.0144	0.003

Karate club

The karate-club social graph already supplied by grip, drawn here with unit edge lengths.

34 vertices; 78 edges. Unit edge lengths.

E <- as.matrix(read.csv(system.file('extdata', 'karate-club-edges.csv', package = 'grip')))
g <- list(n = 34L, edges = E, edge_weights = rep(1, nrow(E)))

Layout	Graph-distance error	Edge-length error	Stage seconds
Metric MDS	0.1505	0.3047	0.019
MDS + edge-KK	0.3268	0.0497	0.002

Generated graphs

A branching tree

A binary tree with shorter edges at greater depth and different lengths for sibling branches. It has no generating coordinates.

63 vertices; 62 edges. Supplied edge lengths.

g <- kary.tree.weighted.graph(k = 2, depth = 5, depth.decay = .85, branch.spread = .2, normalize = 'none')

Layout	Graph-distance error	Edge-length error	Stage seconds
Metric MDS	0.1038	0.3784	0.058
MDS + edge-KK	0.2057	0.0283	0.002

A saddle

A grid lifted to a saddle, with horizontal, vertical, and diagonal edges. Traversal lengths are measured between neighboring surface points. Both layouts are Procrustes-aligned to the gray generating surface. The remaining difference in shape cannot be removed by rotating, reflecting, or translating the layouts while keeping corresponding vertices matched.

100 vertices; 342 edges. Supplied edge lengths.

g <- mesh.surface.graph(10, 10, surface = 'saddle', connectivity = 'diagonal', normalize = 'none')

Layout	Graph-distance error	Edge-length error	Stage seconds
Metric MDS	0.0310	0.0693	0.142
MDS + edge-KK	0.0786	0.0096	0.005

A paraboloid

A grid lifted to a bowl-shaped surface, with horizontal, vertical, and diagonal edges. The diagonals distinguish its graph distances from those of the saddle.

100 vertices; 342 edges. Supplied edge lengths.

g <- mesh.surface.graph(10, 10, surface = 'paraboloid', connectivity = 'diagonal', normalize = 'none')

Layout	Graph-distance error	Edge-length error	Stage seconds
Metric MDS	0.0459	0.0908	0.139
MDS + edge-KK	0.1002	0.0242	0.004

A torus

A grid wrapped around a torus. Connections continue around both circular directions.

96 vertices; 192 edges. Supplied edge lengths.

g <- torus.surface.graph(12, 8, normalize = 'none')

Layout	Graph-distance error	Edge-length error	Stage seconds
Metric MDS	0.0832	0.3222	0.130
MDS + edge-KK	0.2593	0.0003	0.002

Construction examples

These examples retain the distinctive irregular and recursive families from the former website gallery. They compare generating coordinates with weighted GRIP, separately from the saved metric-MDS/edge-KK collection above. These new teaching fits use the stated seed and the current package; they do not extend the saved MDS timing experiment. For these two teaching views only, each fit is translated, rotated/reflected, and uniformly resized to match the generating reference’s root-mean-square radius. The caption reports the display multipliers.

A folded irregular annulus

annulus <- irregular.annulus.surface.graph(rings=5,outer.count=36,
  inner.radius=.42,surface='folded',amplitude=.2)
annulus.fit <- grip(edges=annulus$edges,n=annulus$n,edge.weights=annulus$edge_weights,
  dim=3,metric='edge_length',preset='irregular',seed=4)

Folded annulus: gray generating reference and weighted GRIP. Aligned at a common overall size for display. Display multipliers: Weighted GRIP 0.00728 . Scores use original coordinates.

The inner boundary forces routes around the hole. The gray generating surface helps explain the graph construction; it is not an exact Euclidean realization of every graph distance.

A recursive cross pattern

cross <- vicsek.surface.graph(level=3,surface='ripple',amplitude=.55)
cross.fit <- grip(edges=cross$edges,n=cross$n,edge.weights=cross$edge_weights,
  dim=3,metric='edge_length',preset='carpet',seed=3)

Recursive Vicsek pattern on a rippled surface. Aligned at a common overall size for display. Display multipliers: Weighted GRIP 0.00216 . Scores use original coordinates.

Recursion introduces repeated branches and bottlenecks. For the recorded stages of a related planar recursive construction, see Tracing and diagnosing layouts.