The Central Idea
A network model begins by deciding what the graph should represent.
We choose:
- what objects become vertices;
- what relationships become edges;
- whether direction matters;
- whether edges need weights or capacities;
- which graph questions correspond to the real problem.
The graph is useful only when these modeling choices match the system.
From Real System to Graph
A real-world network can often be summarized as
\[ \boxed{\text{objects}\longrightarrow\text{vertices}} \]and
\[ \boxed{\text{relationships}\longrightarrow\text{edges}}. \]Additional information can then be attached through directions, weights, labels, or capacities.
One System Can Support Several Graph Models
There is rarely only one correct graph for a real system.
A transportation system might be modeled using:
- intersections as vertices and roads as edges;
- cities as vertices and major routes as edges;
- stations as vertices and direct transit services as edges.
The best model depends on the question being asked.
A General Applied Network
Social Networks
In a social network, vertices often represent people, organizations, accounts, or groups.
Edges represent relationships such as:
- friendship;
- communication;
- collaboration;
- following;
- membership overlap;
- transactions or interactions.
Undirected Social Relationships
Some social relationships are naturally symmetric.
If a model records mutual friendship, then
\[ \{u,v\} \]may represent the relationship between people \(u\) and \(v\). No direction is needed.
Directed Social Relationships
Other relationships are asymmetric.
If account \(u\) follows account \(v\), we may write
\[ u\to v. \]The reverse relationship \(v\to u\) need not exist.
Weighted Social Networks
Social edges may carry weights representing relationship strength.
A weight might record:
- number of messages exchanged;
- frequency of collaboration;
- number of shared projects;
- interaction intensity;
- a similarity score.
Degree in a Social Network
Vertex degree gives a simple measure of local connectivity.
In an undirected social graph, \(\deg(v)\) counts the number of direct neighbors of \(v\).
In a directed social graph, in-degree and out-degree distinguish incoming and outgoing relationships.
Local Importance and Centrality
Degree is one basic form of centrality, a family of measures intended to describe structural importance.
Different centrality measures answer different questions.
A vertex with many neighbors may be locally prominent, while another vertex with fewer neighbors may still occupy an important bridge position.
Betweenness Idea
A vertex may be important because many shortest routes pass through it.
Such a vertex can act as an intermediary between otherwise separated regions of a network.
This motivates betweenness centrality, though detailed formulas are beyond the scope of this introductory lesson.
Communities and Clusters
Social networks often contain groups with many internal connections and fewer connections to the rest of the network.
These densely connected regions are often interpreted as communities or clusters.
Graph structure can help detect and compare such groups.
Transportation Networks
Transportation graphs may represent:
- intersections and roads;
- airports and flights;
- rail stations and tracks;
- ports and shipping routes;
- transit stops and direct services.
Direction in Transportation
A two-way road may be modeled by an undirected edge.
A one-way street requires a directed edge.
A network containing both types can be represented using a directed model in which two-way roads appear as one edge in each direction.
Weights in Transportation
Transportation edge weights may represent:
- distance;
- travel time;
- fuel cost;
- toll cost;
- risk;
- congestion penalty.
Different weights can produce different optimal routes through the same physical network.
Shortest Paths in Transportation
If weights measure travel time, then a shortest-path calculation gives a minimum-time route.
If weights measure distance, the same graph structure may produce a different minimum-distance route.
Transportation Capacity
Roads, rails, pipelines, and transit corridors may have capacity limits.
A flow network can model how much traffic or material can move between locations subject to those limits.
Bottlenecks in Transportation
A small-capacity bridge, tunnel, road segment, or transfer point may limit the throughput of an otherwise large network.
Minimum-cut reasoning can identify such structural bottlenecks.
Communication Networks
Communication graphs may represent:
- routers and data links;
- servers and connections;
- devices and wireless links;
- stations and transmission channels;
- software services and message routes.
Reliability and Redundancy
Multiple paths between vertices can provide redundancy.
If one edge fails, an alternate path may preserve connectivity.
Trees provide minimal connectivity, while cyclic networks often provide greater redundancy.
Bridges as Vulnerabilities
A bridge is an edge whose removal disconnects part of a network.
In an infrastructure or communication system, such an edge may represent a single point of failure.
Cut Vertices as Vulnerabilities
A vertex whose removal disconnects the graph is called a cut vertex or articulation vertex.
In a communication network, a cut vertex may represent a critical router, relay, or hub.
Shortest Paths in Communication
Communication routing may assign edge weights based on:
- latency;
- hop cost;
- congestion;
- reliability penalties;
- administrative routing costs.
Shortest-path methods then determine preferred routes under the selected metric.
Flows in Communication
When edge capacities represent data-transfer limits, maximum-flow methods estimate how much information can be transmitted from a source to a destination.
The minimum cut identifies a corresponding capacity bottleneck.
Dependency Networks
A dependency graph represents relationships in which one object depends on another.
Vertices may represent:
- tasks;
- software packages;
- courses;
- manufacturing steps;
- project milestones;
- logical or computational states.
Direction in Dependency Networks
Dependency graphs are naturally directed.
If \(B\) depends on \(A\), one useful convention is
\[ A\to B, \]meaning that \(A\) must be available or completed before \(B\).
The chosen convention should always be stated explicitly.
Dependency Paths
If
\[ A\to B\to C, \]then \(C\) indirectly depends on \(A\).
Directed paths therefore encode chains of dependence.
Cycles in Dependency Networks
A directed cycle can indicate circular dependency.
For example,
\[ A\to B\to C\to A \]means that each item ultimately depends on itself through the cycle.
In many scheduling and build systems, such cycles are invalid.
Directed Acyclic Graphs
A directed graph containing no directed cycles is called a directed acyclic graph, or DAG.
DAGs are natural models for precedence systems in which circular dependencies are forbidden.
Topological Ordering
A topological ordering of a DAG places the vertices in a linear order consistent with all directed dependencies.
If \(u\to v\), then \(u\) appears before \(v\) in the ordering.
This supports scheduling and dependency resolution.
Trees as Dependency Structures
Some dependency systems form rooted trees.
A root may represent a project, file system, or top-level object, while descendants represent subordinate or nested items.
More general dependency systems require DAGs because an item may depend on several predecessors.
Supply and Distribution Networks
Supply networks combine several graph ideas at once.
Vertices may represent suppliers, factories, warehouses, and customers. Edges may carry:
- transportation cost;
- travel time;
- capacity;
- direction;
- reliability information.
Matching in Applied Networks
Bipartite matching applies when one set of objects must be paired with another.
Examples include:
- drivers to routes;
- workers to jobs;
- servers to tasks;
- students to projects;
- vehicles to delivery assignments.
Spanning Trees in Applied Networks
A spanning tree connects every vertex using no cycles.
In a weighted network, a minimum spanning tree may model a low-cost backbone connecting all sites.
The result favors low total infrastructure cost rather than route redundancy.
Planarity in Applied Networks
Some physical networks must avoid crossings or minimize them.
Planarity can matter in:
- circuit-board layouts;
- utility routing;
- road design;
- visual network diagrams.
Coloring in Applied Networks
Graph coloring models conflicts.
If adjacent vertices represent activities that cannot share a resource, colors can represent:
- time slots;
- frequencies;
- channels;
- machines;
- other mutually exclusive resources.
Network Robustness
A robust network continues functioning when some vertices or edges fail.
Useful structural questions include:
- Does an alternate path remain after one edge fails?
- Are there bridges?
- Are there cut vertices?
- How many independent routes connect important vertices?
- Which components become isolated after a failure?
Efficiency and Robustness Can Conflict
A tree uses very few edges and may be inexpensive.
But every edge of a tree is a bridge, so there is no route redundancy.
Adding extra edges costs more but can improve resilience.
Applied network design often balances these competing goals.
Static versus Dynamic Networks
A static network treats vertices, edges, and weights as fixed during the analysis.
A dynamic network may change over time.
Roads close, relationships form, capacities change, and dependencies evolve. The graph model may therefore need repeated updates.
Time-Dependent Weights
An edge weight may depend on time.
Travel time on a road, for example, may be much larger during congestion.
In such systems, the shortest route at one time may not be shortest later.
Uncertainty in Network Data
Real network measurements may be incomplete, delayed, noisy, or estimated.
A mathematically exact graph calculation is only as reliable as the model and data supplied to it.
Applied interpretation should therefore distinguish graph results from uncertainty in the underlying information.
Network Scale
Small graphs can often be inspected directly.
Large networks may contain millions of vertices or edges and require efficient algorithms, data structures, approximation methods, and computational tools.
The mathematical concepts remain the same even when scale changes.
Choosing the Right Graph Question
| Applied Question | Graph Tool |
|---|---|
| Can two locations reach one another? | Connectivity and paths |
| What route has minimum cost? | Shortest paths |
| What is the cheapest network backbone? | Minimum spanning tree |
| How much can move through the network? | Maximum flow |
| Where is the capacity bottleneck? | Minimum cut |
| Can compatible objects be paired? | Matching |
| Can conflicting tasks be separated? | Graph coloring |
| Are circular dependencies present? | Directed cycles |
Model Validation
Before trusting an applied graph result, ask whether the model represents the real system correctly.
Check:
- whether important vertices are missing;
- whether edges represent the intended relationships;
- whether directions are correct;
- whether weights use compatible units;
- whether capacities reflect actual limits;
- whether the network changes over time.
Common Error: Choosing the Wrong Vertex Definition
If vertices represent the wrong objects, later graph calculations may be mathematically correct but practically irrelevant.
Begin every applied network problem by defining the vertex meaning explicitly.
Common Error: Treating a Directed Relationship as Symmetric
A follower relation, prerequisite, one-way road, or message route may work in only one direction.
Converting such relationships to undirected edges can erase essential information.
Common Error: Mixing Weight Meanings
A route calculation cannot meaningfully add miles, minutes, and dollars unless the model deliberately converts them into a common scoring system.
Edge weights used together should represent compatible quantities.
Common Error: Assuming High Degree Means High Importance
Degree measures direct local connectivity.
A lower-degree vertex can still be structurally critical if it is a bridge between communities or a cut vertex in the network.
Common Error: Equating Shortest with Best
The shortest-distance route may not be the fastest, safest, cheapest, or most reliable route.
“Best” depends on what the edge weights measure and what the application values.
Common Error: Ignoring Failure Scenarios
A network may work perfectly under normal conditions but fail badly when one critical edge or vertex is removed.
Robustness analysis should consider alternative paths, bridges, cut vertices, and redundant capacity.
A Reliable Procedure for Applied Network Modeling
- State the real-world question.
- Define what each vertex represents.
- Define what each edge represents.
- Decide whether direction matters.
- Attach weights, capacities, or labels only when they have clear meanings.
- Select the graph concept or algorithm that matches the question.
- Compute the graph result.
- Translate the result back into the real system.
- Check whether the assumptions and data make the interpretation reasonable.
Example: Transportation Workflow
Suppose a city wants the fastest route between two intersections.
Model:
- intersections as vertices;
- permitted road movements as directed edges;
- estimated travel time as edge weight.
The appropriate graph problem is a shortest-path problem using travel time rather than geometric distance.
Example: Communication Workflow
Suppose a network engineer wants the maximum throughput between two nodes.
Model:
- devices or routers as vertices;
- permitted transmission links as directed edges;
- bandwidth limits as capacities.
The appropriate graph problem is maximum flow.
Example: Dependency Workflow
Suppose a build system must determine whether its prerequisites contain a circular dependency.
Model:
- tasks or packages as vertices;
- prerequisite relations as directed edges.
The key question becomes whether the directed graph contains a cycle.
Example: Assignment Workflow
Suppose workers must be assigned to compatible jobs.
Model:
- workers as one bipartite part;
- jobs as the second part;
- compatibility as edges.
The appropriate problem is bipartite matching.
Practice 1: Social Network Direction
A graph records which users follow which other users.
Should the graph normally be directed or undirected?
Practice 2: Transportation Weight
A route-planning system wants the fastest route rather than the shortest geometric route.
What should the edge weights represent?
Practice 3: Communication Bottleneck
A network asks for the greatest data throughput from server \(s\) to server \(t\).
Which graph framework is most appropriate?
Practice 4: Dependency Cycle
A software package \(A\) requires \(B\), \(B\) requires \(C\), and \(C\) requires \(A\).
What graph structure appears?
Practice 5: Assignment
Students must be assigned to compatible projects, with each student and each project used at most once.
Which graph concept models the assignment?
Practice 6: Vulnerability
Removing one communication link disconnects the network.
What type of edge is that link?
Practice 7: Minimal Backbone
Every site must be connected while minimizing total cable-installation cost.
Which graph structure should be sought?
Practice 8: Conflict Scheduling
Two exams are joined by an edge when they have students in common.
What graph method can assign nonconflicting time slots?
Practice 9: Robustness
Why might a network designer intentionally include cycles rather than use a tree?
Practice 10: Identify the Error
A student says, “Vertex \(v\) has the highest degree, so it must be the most important vertex in every possible sense.”
Explain the error.
Practice Answers
Practice 1
Following is generally asymmetric: \(u\to v\) does not imply \(v\to u\).
\[ \boxed{\text{Use a directed graph.}} \]Practice 2
If the objective is minimum travel time, the edge weights should represent
\[ \boxed{\text{travel time}}. \]Practice 3
Throughput subject to capacity limits is modeled using
\[ \boxed{\text{network flow}}. \]Practice 4
The dependencies form
\[ A\to B\to C\to A. \]This is a
\[ \boxed{\text{directed cycle}}. \]Practice 5
The two object types form the two parts of a bipartite graph, and the goal is a
\[ \boxed{\text{matching}}. \]Practice 6
An edge whose removal disconnects the graph is a
\[ \boxed{\text{bridge}}. \]Practice 7
Connecting all sites while minimizing total selected edge cost is a minimum-spanning-tree problem:
\[ \boxed{\text{minimum spanning tree}}. \]Practice 8
Adjacent exams must receive different time-slot labels, so use
\[ \boxed{\text{graph coloring}}. \]Practice 9
Cycles can provide alternate routes. If one edge fails, another path may preserve connectivity.
\[ \boxed{\text{Cycles can improve redundancy and resilience.}} \]Practice 10
Degree measures only direct local connectivity.
Other vertices may be more important by measures involving shortest paths, bottlenecks, community bridges, flow, or vulnerability.
\[ \boxed{\text{Importance depends on the structural question being asked.}} \]What to Remember
- Applied network modeling begins by defining vertices and edges precisely.
- Direction, weights, and capacities should reflect the real relationship being modeled.
- Social networks may be directed, undirected, weighted, or combinations of these.
- Transportation networks commonly use weighted shortest paths and capacity models.
- Communication networks use connectivity, redundancy, shortest paths, flows, bridges, and cuts.
- Dependency networks are naturally directed and often modeled as DAGs when cycles are forbidden.
- Matching models one-to-one assignments between compatible objects.
- Spanning trees model minimal full connectivity, while extra cycles can provide resilience.
- Graph coloring models conflicts and shared-resource constraints.
- A graph calculation must always be interpreted in light of the model's assumptions and data.
Where We Go Next
This lesson completes the core Graphs, Trees, and Networks sequence by bringing its structural tools together in applied settings.
The larger discrete and stochastic program will continue building on these ideas whenever relationships, states, routes, dependencies, optimization, or networked systems appear.