Representing Possible Information Flow
A social network can be represented as a directed graph when following relationships have a direction. That direction matters: a person who follows an account may receive its posts, but the account does not thereby receive posts from that follower. To trace possible information flow, the graph’s arrows must point in the direction in which information could pass.
Throughout, graphs are finite and simple. A directed graph has vertices and directed edges, also called arcs; there is at most one arc from one vertex to another, and there are no loops. In the model used here, an arc \(u\to v\) means that \(v\) follows \(u\), so a message from \(u\) could be passed to \(v\). This is a modelling convention, not a claim that a platform necessarily delivers every message.
For reachability, allowing walks instead of paths would not change which vertices can be reached: if a walk repeats a vertex, the section between two occurrences can be removed, leaving a shorter directed walk with the same endpoints. Repeating this deletion gives a path. A length counts arcs, not the number of vertices in a path. Thus a path with \(s\) and \(v\) as its two vertices has length \(1\).
The set of vertices at distance \(i\) from \(s\) is the breadth-first layer \(L_i=\{v:d(s,v)=i\}\). Layer \(L_0\) contains just \(s\). Some layers may be empty, and vertices in no layer are unreachable from \(s\). Breadth-first search (BFS) constructs these layers by examining outgoing arcs in order of increasing distance.
How Breadth-First Search Finds the Layers
Start by assigning \(s\) label \(0\), marking it discovered, and placing it in a queue. Repeatedly remove the first vertex \(u\) in the queue and inspect its outgoing neighbors. For each neighbor \(v\) not already discovered, mark \(v\) discovered, assign it label \(d(u)+1\), and add it to the end of the queue. Stop when the queue is empty. A vertex is marked when it is added, not when it is later removed, so it is never added twice.
Proof. First, every label assigned by BFS is the length of a directed path from \(s\). The initial label \(0\) corresponds to the path consisting of \(s\). If \(u\) has a path of length \(k\) and BFS discovers \(v\) while inspecting an arc \(u\to v\), appending that arc gives a path of length \(k+1\). Thus a discovered vertex with label \(k\) has distance at most \(k\).
Next, vertices are removed from the queue in nondecreasing order of their labels. Initially this holds because the queue contains only \(s\). When a vertex of label \(k\) is removed, every newly added vertex has label \(k+1\); vertices already waiting have label \(k\) or \(k+1\). Adding the new vertices at the end therefore preserves nondecreasing order.
We now show that every vertex reachable from \(s\) is discovered with its correct label. Use induction on its distance \(i\). The vertex \(s\), at distance \(0\), is discovered with label \(0\). Suppose every vertex at distance \(i-1\) has been discovered with that label, and take \(v\) at distance \(i\). A shortest path to \(v\) has a predecessor \(u\) at distance \(i-1\), followed by the arc \(u\to v\). BFS eventually removes \(u\), since the queue processes finitely many discovered vertices and each vertex is added at most once. When it inspects \(u\to v\), either \(v\) was already discovered or it is assigned a label at most \(i\): the queue order ensures no vertex of label greater than \(i-1\) is processed before \(u\). The path represented by the label shows \(d(s,v)\leq\text{label}(v)\). Since \(d(s,v)=i\), a label at most \(i\) must equal \(i\). This proves the induction step. Finally, BFS discovers only vertices reached by the paths represented by their labels, and the induction shows it discovers every reachable vertex. \(\square\)
The proof explains why a queue is important. It ensures that shorter paths are examined before longer ones. The labels are not guesses about influence or popularity; they are exact minimum arc counts in the directed graph.
Worked Example: Finding Everyone Reachable from an Account
Let the users be \(V=\{A,B,C,D,E,F,G,H\}\), with arcs \(A\to B,A\to C,B\to D,B\to E,C\to E,C\to F,D\to G,E\to G,F\to G,G\to B,H\to A\). An arc points from the account whose information may be passed on to the follower. Run BFS from \(A\). Inspect each vertex’s outgoing neighbors in alphabetical order.
| Action | New discoveries and labels | Queue after action |
|---|---|---|
| Initialize | \(A:0\) | \(A\) |
| Remove \(A\) | \(B:1,\ C:1\) | \(B,C\) |
| Remove \(B\) | \(D:2,\ E:2\) | \(C,D,E\) |
| Remove \(C\) | \(E\) is already discovered; discover \(F:2\) | \(D,E,F\) |
| Remove \(D\) | \(G:3\) | \(E,F,G\) |
| Remove \(E\) | \(G\) is already discovered | \(F,G\) |
| Remove \(F\) | \(G\) is already discovered | \(G\) |
| Remove \(G\) | \(B\) is already discovered | empty |
The resulting layers are \(L_0=\{A\}\), \(L_1=\{B,C\}\), \(L_2=\{D,E,F\}\), and \(L_3=\{G\}\). Vertex \(H\) is not discovered. The arc \(H\to A\) allows information to flow from \(H\) to \(A\), not from \(A\) to \(H\). The cycle \(B\to D\to G\to B\) does not create a new route to an undiscovered vertex.
Check: The labels have path witnesses: \(A\to B\), \(A\to C\), \(A\to B\to D\), \(A\to B\to E\), \(A\to C\to F\), and \(A\to B\to D\to G\) have lengths \(1,1,2,2,2,3\), respectively. No arc goes from \(A\) directly to a vertex in \(L_2\), and the only ways into \(G\) from reachable vertices come from \(D,E,F\), all at distance \(2\). So the displayed labels cannot be reduced. There is no directed path from \(A\) to \(H\), since no arc enters \(H\).
Direction and Minimum Distance
Reachability is directional. Even if two users are joined by an arc, only its tail can pass information along that arc to its head. More generally, reversing every arc can change both the reachable set and the distances. A follower relationship should therefore not be treated as an undirected connection when the question concerns who could receive a message from a particular source.
Worked Example: An Incoming Arc Does Not Give a Route Out
Let \(V=\{M,N,P,Q\}\) and \(E=\{M\to N,N\to P,P\to M,Q\to N\}\). Starting at \(M\), the length-zero path reaches \(M\), the arc \(M\to N\) reaches \(N\) in one step, and \(M\to N\to P\) reaches \(P\) in two steps. The arc \(P\to M\) returns to an already reachable vertex. There is no arc entering \(Q\), so \(Q\) is not reachable from \(M\). Thus the distances are \(d(M,M)=0\), \(d(M,N)=1\), \(d(M,P)=2\), and \(d(M,Q)=\infty\).
The arc \(Q\to N\) means that \(Q\) can pass information to \(N\). It does not provide a path from \(M\) to \(Q\), and it does not make \(Q\) a one-step recipient of \(M\)’s information. Conversely, the directed cycle \(M\to N\to P\to M\) allows each of \(M,N,P\) to reach the other two, but does not connect \(Q\) in the direction needed.
Check: The listed paths from \(M\) have lengths \(0,1,2\). There is no arc \(M\to P\), so \(P\) cannot be reached in one step; the only arc entering \(P\) is \(N\to P\), which requires first reaching \(N\). Since \(Q\) has no incoming arc, no positive-length path from \(M\) can end at \(Q\).
Distance is a minimum. A longer route may also exist, but it does not increase the BFS label. This matters when several routes carry the same information: the graph distance records the fewest forwarding links, not the number of routes, the probability of delivery, or the time taken in a real platform.
Worked Example: Comparing Two Routes to the Same User
Let \(V=\{S,A,B,C,D\}\) and \(E=\{S\to A,S\to B,A\to C,B\to C,C\to D,A\to D\}\). From \(S\), vertices \(A\) and \(B\) are at distance \(1\). Vertex \(C\) is at distance \(2\), by either \(S\to A\to C\) or \(S\to B\to C\). Vertex \(D\) is at distance \(2\) by \(S\to A\to D\). There is also a longer route \(S\to B\to C\to D\), of length \(3\), but the distance to \(D\) remains \(2\).
Check: The outgoing arcs from \(S\) end only at \(A\) and \(B\), so neither \(C\) nor \(D\) can be reached in one step. The arc \(A\to D\) supplies a two-step path to \(D\), establishing \(d(S,D)=2\); the length-three route cannot be a shorter one. The distance layers are \(\{S\},\{A,B\},\{C,D\}\).
When Layers Represent Forwarding Rounds
A graph by itself describes possible routes. To interpret the distance labels as rounds of information spread, add a specific process assumption: at round \(0\), only \(s\) knows the information; at each subsequent round, every person who knows it sends it to all of their outgoing neighbors; each such transmission succeeds and takes one round. A recipient who already knows the information need not receive it again. Under these assumptions, the distance to a vertex is exactly its first round of receipt.
Proof. We use induction on \(k\). At round \(0\), precisely \(s\) knows the information. This is exactly the set of vertices with distance at most \(0\). Suppose the statement holds at the end of round \(k\). During the next round, each vertex that already knows the information can send it along every outgoing arc. Thus the newly informed vertices are precisely those at the head of an arc whose tail has distance at most \(k\), except for vertices already informed. Each newly informed vertex has a path from \(s\) of length at most \(k+1\), so its distance is at most \(k+1\). Conversely, if \(d(s,v)\leq k+1\) but \(v\) was not informed by round \(k\), a shortest path to \(v\) has a penultimate vertex \(u\) with \(d(s,u)\leq k\) and an arc \(u\to v\). By the induction hypothesis \(u\) knows the information by round \(k\), so it sends it to \(v\) in the next round. Therefore \(v\) is informed by the end of round \(k+1\). This proves the claim for every \(k\). A vertex with no directed path from \(s\) cannot be informed by this rule, because every transmission follows an arc and a sequence of transmissions would give a directed path from \(s\). \(\square\)
For the graph in the previous example, the theorem says \(A\) and \(B\) receive the information in round \(1\), while \(C\) and \(D\) receive it by round \(2\), assuming all transmissions succeed. The longer route to \(D\) does not delay its first receipt because the shorter route \(S\to A\to D\) is available.
What the Graph Does—and Does Not—Say
Reachability is a structural conclusion: there is a directed path in the model. It does not prove that anyone saw, read, believed, or forwarded a post. Nor does distance alone measure influence, audience size, or likelihood of transmission. The equal-one-round assumption is also a simplification; if forwarding delays vary, shortest unweighted path length need not describe earliest arrival.
In an application, the conclusion should be stated at the level supported by the model. For example, “\(D\) is two forwarding links from \(S\)” follows from the example’s graph. “\(D\) will receive the post after two rounds” additionally requires the forwarding and successful-delivery assumptions. “\(D\) will share it” requires behavioral evidence that the graph does not contain.
Common mistake: reversing an arc. In the graph \(M\to N,N\to P,P\to M,Q\to N\), it is wrong to read \(Q\to N\) as a route \(N\to Q\) and conclude that \(Q\) is one step from \(M\). The correct directions give \(M\to N\to P\) and no path from \(M\) to \(Q\). Always follow arrows from tail to head; an edge incident with a reachable vertex does not automatically make its other endpoint reachable.
Check Your Understanding
For each question, use the stated arrow directions and distinguish what follows from the graph from what would require an assumption about behavior.
- Let \(V=\{X,Y,Z\}\) and \(E=\{X\to Y,Z\to Y\}\). From source \(X\), which vertices are reachable, and what is each finite distance?
- Give a directed graph in which a vertex has both a path of length \(3\) and a path of length \(2\) from the source. What is its distance?
- In BFS, why must a newly discovered vertex be marked when it is added to the queue rather than when it is removed?
- State the extra assumptions needed to interpret distance \(4\) as receipt in round \(4\).
- Explain why a directed path from \(s\) to \(v\) establishes possible graph reachability but does not establish that \(v\) actually receives or forwards a message.