IS6335 Chap.8 Network Data Structures and Graph Visualization
Network Data Structures and Graph Visualization
Where the value belongs to a relationship
Week eight opens the third dataset family. The published topics are the network data structure, network visualization examples, and the adjacency matrix and edge list, with an R tutorial on igraph. The vocabulary is small and worth fixing exactly: an item in a network is a node, also called a vertex, and a connection between two of them is a link, also called an edge.
Nodes and links can each carry attributes, and deriving a node attribute from the structure itself, then encoding it on colour or size, is the standard way to make a drawing say something.
Three ways to write down the same graph
An edge list records one row per link, naming its two ends. An adjacency matrix puts every node on both axes and marks the cell where two connected nodes meet.
A node-link drawing places nodes in space and draws links between them. These are the same information in three containers, and choosing between them is the central decision of this week and the next.
Each is cheap at something different. An edge list is cheap to store, filter and stream, and a link can be added without touching anything else; it is not a view at all, so it shows nothing.
An adjacency matrix makes it easy to read whether two named nodes are connected and to spot dense blocks, and it makes following a path of more than one step expensive.
A node-link drawing makes paths easy to follow and clusters and isolated nodes visible, and it becomes unreadable once the graph is dense.
Seven topologies, and what each one is fragile to
Topology was listed as a target in week two: a question about the overall shape of the connections rather than about any particular one.
The course names seven shapes to recognise, which are the ring, the mesh, the star, the fully connected graph, the line, the tree and the bus. Recognising which you have answers a robustness question with no computation at all.
A star breaks completely if its centre is removed and not at all if any other node goes.
A ring survives any single break, because two routes connect every pair, and splits in two if a second occurs. A tree has exactly one route between any pair, so every internal node is a single point of failure for everything below it. A mesh connects many nodes to many others without a single centre, so it degrades gradually. A line is a chain with two ends and no redundancy.
A fully connected graph is maximally robust and maximally expensive, which is why it is only ever seen at small node counts. When a stakeholder asks what would happen if a supplier or a server were lost, the topology is often the whole answer.
A layout is not a topology
Force-directed layout algorithms are randomised, so running one twice on the same graph produces two different pictures.
Anything claimed from the picture has to survive re-running the layout, and a cluster that disappears on the second run was an artefact of the algorithm rather than a property of the network.
Two nodes that look close in a drawing are not necessarily close in the graph.
The point where a drawing stops working
Week one used a gene interaction diagram to illustrate what it called messy big data: a network drawn with so many nodes and links that nothing can be read.
The failure is driven by links per node rather than by node count alone, which is why a large sparse graph can still be drawn and a small dense one often cannot.
Three responses exist. Filtering keeps only links above a weight threshold; it works when link strength is meaningful and it silently changes the topology, so the threshold has to be reported.
Aggregating replaces groups of nodes with one node each; it preserves the overall shape and destroys every within-group question. Changing idiom to an adjacency matrix is the third, and it is the subject of the next chapter, because a matrix never becomes a hairball: its layout does not depend on the links at all.
What this chapter covers
- 01
Nodes, vertices, links and edges
- 02
Edge list, adjacency matrix and node-link drawing
- 03
What each of the three forms is cheap and expensive at
- 04
The seven named topologies
- 05
Topology as a robustness claim made without computation
- 06
Why a force-directed layout has to be re-run
- 07
Link density as the driver of the hairball failure
- 08
Filtering, aggregating and changing idiom
Decide what a dense collaboration graph can support
- 2Rule on the node-link drawing and give the reason.
- 3Describe the filtering route and its reporting obligation.
- 3Describe the aggregation route and what makes it believable.
Key terms
- Edge list
- A network written as one row per link, naming its two ends. It stores and streams cheaply and shows nothing until it is turned into a matrix or a drawing.
- Node-link drawing
- A network drawn with nodes placed in space and links between them. It makes paths traceable and degrades badly as links per node rise.
- Force-directed layout
- A randomised algorithm that positions nodes by simulated attraction and repulsion. Two runs give two pictures, so any claim read from one has to survive the second.
- Network topology
- The overall shape of the connections, independent of any particular link. Naming it answers a robustness question without computation.
- Link density
- Links per node. It, rather than the number of nodes, is what decides whether a node-link drawing remains readable.
Network Data Structures and Graph Visualization FAQ
My data is a spreadsheet of emails. Is that a network?
It is already an edge list, with sender and recipient as the two ends of each link, and two derivations are needed before anything can be drawn. Repeated emails between the same pair must be collapsed into one link carrying a count, otherwise the same link is drawn hundreds of times and the picture reports volume as clutter.
And a decision has to be made about direction, because sender to recipient is directed and treating the relationship as undirected merges two different things into one. Both decisions belong in the write-up, since a reader cannot see either of them in the finished drawing.
Two clusters sit next to each other in my diagram. Can I say they are related?
Not from the picture alone. Re-run the layout with a different random seed first; if the clusters separate, the adjacency was an artefact. If they stay adjacent, go back to the edge list and count the links that actually run between them, then compare that count with the links each cluster has inside itself.
Proximity in a force-directed drawing follows from links, but it also follows from having nowhere else to go, and only the counted comparison distinguishes the two.
Assessment move
Build one small graph of your own, about a dozen nodes, and write it in all three forms by hand: an edge list, a matrix and a drawing. Doing it once makes the trade-offs concrete in a way that reading about them does not, and you will be able to see immediately why a path is easy in one form and painful in another.
Keep it, because the same small graph is the cleanest thing to test any igraph command on before you point it at the project data.
Working through Network Data Structures and Graph Visualization in IS6335? Sia is AskSia’s AI Information Technology tutor — ask any IS6335 Network Data Structures and Graph Visualization question and get a clear, step-by-step explanation grounded in how IS6335 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
