How Network Science and Graph Analysis Work

Five places can contain the same roads and still tell very different stories depending on which way the roads run, how costly they are to cross and which connections disappear during failure. Counting places is not enough. The pattern between them matters.

Network science studies systems whose structure is represented by entities and relationships. Graph analysis turns that representation into questions about connection, reachability, paths, centrality, clustering, communities, flow, diffusion, robustness and change over time.

This article owns structural network analysis. Knowledge Graphs and Semantic Data owns machine-readable meaning, ontologies and semantic relations. Graph Tokenisation owns how graph structures become model-ready units. Biology, Medicine and Veterinary retain their specialist network applications. Here the subject is the general mathematical and analytical structure of networks.

All worked networks below are invented teaching examples. They do not represent eduKate students, real social relationships, clinical networks or operational infrastructure.

Reading route: begin with graph grammar, work through a five-node network, compare centrality measures, then explore communities, diffusion, resilience, time and the final network-analysis checklist.

1. A graph is a representation, not the system itself

A graph normally contains a set of nodes, also called vertices, and a set of edges connecting pairs of nodes. The notation G=(V,E) is compact; the modelling decision behind it is not.

A city can be represented with intersections as nodes and roads as edges. A research network can use authors and coauthorships. A computer network can use devices and communication links. The same real system can support several graphs because different questions require different definitions of node and edge.

2. Node identity must be stable before analysis begins

If “Central Library”, “Main Library” and one building identifier all refer to the same place, counting them as three nodes creates false degree, false paths and false communities.

Network analysis therefore depends on entity resolution and identity. Use Record Linkage and Entity Resolution when names, aliases and identifiers must be reconciled before the graph is constructed.

3. Edge meaning is as important as node meaning

An edge can mean friendship, shipment, citation, ownership, communication, dependency, adjacency or shared membership. These relations are not interchangeable.

Combining unlike relations into one undifferentiated edge can produce a graph that is easy to draw and difficult to interpret. Define what relationship must exist, over what time interval and with what evidence before counting it.

4. Directed and undirected graphs answer different questions

A friendship representation may be treated as undirected when the relation is mutual. A citation is directed: Paper A can cite Paper B without B citing A. A road network may contain one-way links.

Direction changes reachability, in-degree, out-degree, paths and centrality. Removing arrows because an undirected algorithm is easier to run can remove the mechanism the graph was supposed to preserve.

5. Weighted edges need a declared interpretation

An edge weight can mean distance, travel time, cost, capacity, frequency, probability or strength. Larger weight can therefore mean either stronger connection or harder traversal depending on the field.

A shortest-path algorithm that interprets a high value as a long distance should not receive “relationship strength” weights without transformation. The arithmetic may run while the meaning reverses.

6. Multigraphs preserve several edges between the same nodes

Two places may be connected by road, rail and data fibre. Two organisations may have several contracts. Collapsing these into one edge can hide redundancy or dependency.

A multigraph or multilayer model can preserve distinct connection types when the analysis depends on them. The extra complexity should serve a real question rather than decorate the model.

7. Build a five-node teaching network

Consider an undirected unweighted graph with nodes A, B, C, D and E and edges:

A—B
A—C
B—C
C—D
D—E

A, B and C form a triangle. C connects that triangle to D, and D connects onward to E. The network has five nodes and five edges.

This tiny graph will let us see why different network measures answer different questions.

8. Degree counts direct connections

In the toy graph, degree(A)=2, degree(B)=2, degree(C)=3, degree(D)=2 and degree(E)=1. C has the largest degree because it touches A, B and D directly.

Degree can represent immediate exposure or local connectivity. It says nothing by itself about whether those neighbours are important, whether the node lies between distant groups or whether the edges are reliable.

9. Degree centrality normalises local connection by network size

In a simple undirected graph of n nodes, degree centrality is commonly degree divided by n−1. With five nodes, C has degree centrality 3/4 = 0.75 and E has 1/4 = 0.25.

Current NetworkX centrality documentation provides implementations of degree, closeness, betweenness, eigenvector and related measures. The variety is itself a warning: there is no universal “importance score” for networks.

10. Paths describe routes through the network

A path is a sequence of adjacent nodes or edges connecting a source to a target. In the toy graph, A-C-D-E is a path from A to E of length three edges.

A path need not be a physical route. It can represent a chain of citations, dependencies or transmissions if the edge meaning supports that interpretation.

11. Shortest path depends on what edge weight means

In an unweighted graph, shortest path commonly means fewest edges. In a weighted graph it can mean minimum total distance or cost.

The current NetworkX shortest-path guide distinguishes unweighted and weighted paths and notes different algorithms for different edge conditions, including Dijkstra, Bellman–Ford and Floyd–Warshall families.

12. A minimum-hop route can be a bad operational route

Two roads may create a two-edge path that takes an hour, while three faster roads create a three-edge path taking twenty minutes. If travel time matters, counting edges is the wrong cost function.

Network analysis inherits the same optimisation lesson: define what “short” means before asking the algorithm to find the shortest route.

13. Reachability asks whether a route exists at all

Two nodes can be connected by many routes, one route or none. In directed graphs, A may reach B while B cannot reach A.

Reachability is fundamental for supply, communication and dependency analysis because a node with high degree can still be unable to reach a critical target if direction or layer restrictions block the path.

14. Components reveal disconnected regions

An undirected graph’s connected components partition nodes into groups with paths inside each group and no paths between groups. In directed graphs, weak and strong connectivity answer different questions.

A disconnected component can represent isolation, a data defect or an intentionally separate system. The graph cannot decide which explanation is correct.

15. Betweenness centrality asks who lies on shortest routes between others

C and D are structurally important in the toy graph because every route between the triangle {A,B,C} and E passes through both of them.

Betweenness centrality counts the fraction of shortest paths between pairs that pass through a node. NetworkX’s current betweenness-centrality documentation defines the measure in terms of shortest-path counts.

A high-betweenness node can be a broker, bridge or vulnerability. The interpretation depends on what flow, if any, actually follows shortest paths.

16. Removing a bridge can fragment the graph

Remove edge C-D from the toy graph and {A,B,C} becomes disconnected from {D,E}. The edge is a bridge: its removal increases the number of connected components.

Bridge detection can reveal single points of structural dependence. It should not be confused with proof that real operations will fail, because alternative channels may exist outside the represented graph.

17. Closeness centrality asks about average distance to others

A node with high closeness can reach other reachable nodes through relatively short paths. This can matter for dissemination or access when shortest-path distance is meaningful.

Disconnected graphs complicate closeness, and directed graphs require careful attention to inward versus outward distance. Never compare closeness scores without checking the exact convention used.

18. Eigenvector centrality values connections to well-connected nodes

Degree treats every neighbour equally. Eigenvector centrality gives more weight to connections with nodes that are themselves central under the recursive definition.

This can capture prestige-like structure, but it can behave unintuitively in directed, disconnected or unusual graphs. A recursive score is not automatically a measure of social value, truth or authority.

19. PageRank adds direction and random-walk ideas

PageRank is one influential centrality family for directed networks. It can be interpreted through a random surfer moving along links with occasional teleportation.

Its success in web search does not make it the correct centrality for every citation, transport or dependency network. The measure must match the process being modelled.

20. Centrality is question-dependent, not person-dependent

The same node can rank high in degree, low in betweenness and moderate in closeness. Those are not contradictory results. They describe different structural roles.

Ask “central for what mechanism?” before interpreting a ranking. A route broker, popular neighbour and globally accessible node are different positions.

21. Density counts how many possible edges are present

For a simple undirected graph with n nodes, at most n(n−1)/2 edges are possible. With five nodes, there are ten possible edges. Our toy network has five, giving density 0.5.

Density can fall as networks grow even when average degree rises. Compare like with like and consider whether every node pair could meaningfully have formed an edge.

22. Clustering asks whether neighbours are connected to each other

A and B are both neighbours of C, and they are connected to each other. This triangle creates local clustering around C.

High clustering can indicate cohesive neighbourhoods, redundant routes or triadic closure, depending on the domain. It can also arise mechanically from the way data were collected.

23. A community is a pattern, not a natural label guaranteed by the data

Community-detection methods search for groups that are more densely or strongly connected internally than expected under a particular criterion or model.

Different algorithms can return different partitions. A community is therefore partly an analytical object produced by a method, resolution and graph definition, not automatically a real-world group with one true boundary.

24. Modularity compares within-group structure with a null expectation

Modularity is a common quality function for evaluating partitions relative to a null model of expected connections. Optimising modularity can reveal useful mesoscale structure.

But modularity has known resolution limitations and can admit many near-optimal partitions. Report the method and test stability rather than presenting one coloured network diagram as the only possible truth.

25. Communities can overlap

A researcher can belong to several fields. A logistics hub can serve several corridors. A person can participate in several social groups.

A partition that forces every node into exactly one community may therefore be convenient rather than realistic. Use overlapping or multilayer representations when the reader job requires them.

26. Assortativity asks whether similar nodes connect

Networks can exhibit assortative mixing when nodes with similar attributes or degree tend to connect, or disassortative mixing when unlike nodes connect more often.

Correlation in connections does not identify why the pattern formed. Preference, institutional rules, geography and opportunity can produce similar network statistics.

27. Degree distributions summarise connectivity heterogeneity

Some networks have narrowly concentrated degrees; others contain many low-degree nodes and a few hubs. Degree distribution is a useful descriptive object.

Do not label a network “scale-free” merely because a log-log plot looks approximately straight. Distribution fitting and model comparison require statistical care.

28. Random-graph models create baselines for comparison

A network statistic becomes more meaningful when compared with a plausible null model. Is the observed clustering larger than expected for a random graph with similar size and degree structure?

The null model must preserve the features that should not count as surprising. A badly chosen baseline can make ordinary structure look exceptional.

29. Small-world structure combines short paths with local clustering

Small-world models show how a network can maintain local neighbourhood structure while a limited number of long-range links dramatically shorten typical paths.

This helps explain why adding a few connector edges can change reachability far more than adding the same number of redundant local edges.

30. Preferential attachment is one growth mechanism, not a universal origin story

In preferential-attachment models, new nodes are more likely to connect to nodes that already have many connections. This can create highly unequal degree patterns.

Real networks can acquire hubs through geography, capacity, policy, age, fitness or measurement effects as well. Observing a heavy-tailed degree pattern does not prove preferential attachment caused it.

31. Diffusion depends on network structure and process rules

Information, behaviour, failures and contagion can spread along networks, but not by one universal mechanism. Some processes require one exposure; others require repeated reinforcement. Some edges transmit readily; others rarely.

Network structure shapes opportunities for spread. The process model determines what happens when an exposure occurs.

32. Simple contagion and complex contagion behave differently

A simple contagion model may allow one contact to transmit. A complex contagion may require several neighbours, social proof or reinforcement before adoption.

The same high-degree node can be influential under one mechanism and ineffective under another. Do not import epidemic intuition into social adoption without checking the process.

33. Central nodes are not always the best seeds

If influence saturates within one community, choosing several highly connected nodes from the same cluster may waste coverage. A more dispersed seed set can reach more communities.

Seed selection is an optimisation problem on a network and depends on the diffusion model. Centrality rankings alone do not solve it.

34. Network observation is not causal identification

Friends can resemble one another because they influence each other, because similar people become friends, because they share environments or because the data contain selection bias.

A network association does not by itself identify peer influence. Use Causal Inference for the additional assumptions and designs needed to support causal claims.

35. Robustness asks what survives when nodes or edges fail

Remove random nodes and measure the size of the largest connected component, reachability, average path length or service flow. Then compare targeted removal of high-degree or high-betweenness nodes.

Different failure strategies reveal different vulnerabilities. A network robust to random loss can be fragile to targeted removal of hubs or bridges.

36. Structural redundancy can create resilience

If two independent paths connect critical regions, one edge failure may leave a route. Redundancy can therefore improve connectivity resilience.

But duplicate-looking paths can share one hidden dependency such as power, ownership or geography. Graph resilience depends on whether the representation includes common-mode failures.

37. Cascades require a load or dependency model

When one component fails, its load may shift to others. Those components can overload and fail in turn. A pure topology graph does not contain that mechanism unless capacities and redistribution rules are added.

Cascade analysis therefore joins network structure to dynamic models and simulation.

38. Percolation asks about large-scale connectivity under removal or occupation

Percolation-style models examine how global connectivity changes as nodes or edges are randomly occupied, activated or removed.

Threshold behaviour can reveal when a network moves from fragmented pieces to a giant connected component, but real systems may violate the independence and randomness assumptions of simple percolation models.

39. Static networks can hide sequence

Suppose A contacts B on Monday and B contacts C on Sunday. A static graph contains A-B-C and suggests a path. If the process requires information to move forward in time, that path may or may not be usable depending on event order.

Temporal networks preserve timestamps or intervals so reachability respects chronology.

40. Aggregating across time can create edges that never coexisted

A yearly network can connect everyone who interacted at any point during the year. That can be useful for exposure history and misleading for simultaneous capacity or real-time diffusion.

Choose the time window according to the mechanism, then test whether conclusions change when the aggregation interval changes.

41. Multilayer networks preserve different relationship channels

The same entities can interact through transport, finance, communication and ownership layers. A failure in one layer can affect another.

Cambridge University Press’s Multilayer Network Science reviews the representation and analysis of systems whose units interact in several ways simultaneously.

42. Bipartite graphs keep two entity types separate

A bipartite network can connect learners to activities, authors to papers, or suppliers to products without creating direct same-type edges.

Projecting a bipartite graph onto one node type can be useful, but it creates derived edges. Two authors become connected because they share a paper; that projected edge is not an independently observed relationship.

43. Hypergraphs represent relationships involving more than two nodes at once

A paper with six authors is one six-way collaboration event. Pairwise projection turns it into fifteen author-author edges and can overstate how many independent collaborations occurred.

Hypergraphs and higher-order network models preserve multi-entity relations when pairwise edges lose essential structure.

44. Missing edges are not the same as absent relationships

A graph contains what the data collection process observed and encoded. An absent edge may mean no relationship, an unobserved relationship, a filtered relationship or one that occurred outside the chosen time window.

This is the network form of missing-data reasoning. Use Missing Data Analysis when observation mechanisms can affect the graph.

45. Sampling a network can distort its structure

Sampling nodes, edges or snowball referrals can alter degree distributions, path lengths, components and centrality. A network statistic calculated precisely on a biased subgraph may be precisely wrong for the target network.

Report how the network was observed, not only how it was analysed.

46. Privacy risk can arise from structure itself

Removing names from a network does not automatically anonymise it. Unique structural patterns and auxiliary information can support re-identification.

Network data involving people therefore requires privacy review at the graph level, not merely deletion of direct identifiers.

47. Visualisation can reveal structure and invent emphasis

Force-directed layouts place connected nodes near one another, but the visual distance is produced by a layout algorithm. It is not automatically physical, social or causal distance.

Node size, colour and edge thickness can dominate interpretation. Use Data Visualisation to preserve scale, uncertainty and accessible design.

48. Network metrics need null models and uncertainty where appropriate

A centrality score is often computed exactly for the observed graph, but the observed graph can itself be one noisy sample of a larger process. Edge uncertainty, sampling variability and temporal instability can matter more than numerical precision.

Bootstrap, permutation or model-based approaches may help quantify uncertainty when their assumptions fit the network problem. Use Bootstrap and Resampling with care because ordinary independent resampling can break network dependence.

49. A network can be descriptive, predictive, causal or prescriptive

Descriptive analysis asks what structure exists. Predictive analysis uses network features to forecast. Causal analysis asks whether relationships or interventions change outcomes. Prescriptive analysis chooses actions on the network.

Do not slide between these jobs. Finding a central node does not prove that intervening on it will cause the largest improvement.

50. Network optimisation is a neighbouring owner, not the same task

Shortest paths, maximum flows, minimum-cost flows, matchings and routing choose actions on graph structure. These are optimisation problems.

The new Linear Programming and Mathematical Optimization article owns the general choice machinery. This article owns the network’s structure and the measures used to understand it.

51. Working with network data requires an evidence pipeline

Cambridge University Press’s Working with Network Data emphasises gathering, processing and interpreting network data rather than treating algorithms as the entire workflow.

A reliable network analysis preserves source, collection rule, time window, identity resolution, edge definition, transformations, graph version, algorithm version and interpretation boundary.

52. A graph audit should work backward from the claim

NETWORK CLAIM
→ METRIC OR MODEL
→ GRAPH VERSION
→ NODE AND EDGE DEFINITIONS
→ FILTERS / PROJECTIONS
→ ENTITY RESOLUTION
→ SOURCE RECORDS
→ OBSERVATION PROCESS
→ REAL SYSTEM

If that route cannot be reconstructed, a beautiful graph can be weak evidence.

54. The deeper lesson: connection creates a second layer of reality

Two systems can contain the same parts and behave differently because the parts are connected differently. Network science makes that relational layer visible.

The graph is useful when it preserves the relationships that matter to the question, distinguishes observation from inference and returns its conclusions to the world for checking. A network is not important because it has many edges. It is important because structure changes what can reach what, what can fail together and what one local action can become when it travels through connections.

Sources and further reading

This is an explanatory synthesis with original hypothetical examples. Source pages were checked for this edition on 5 September 2026.

Continue through eduKate: use Knowledge Graphs and Semantic Data for machine-readable meaning, Graph Tokenisation for model-ready graph units, Causal Inference for intervention claims, and Data Visualisation for reader-safe presentation. Return to the Research Collections Directory for the wider research route.

How Network Science and Graph Analysis Work | Nodes, Edges, Paths, Centrality, Communities, Diffusion and Resilience