A directed graph often records who acts on whom. In a social network, for example, an arrow can mean that one member influences another. Once the arrows are written into an adjacency matrix, a few matrix operations tell you which member has the widest influence. I'll first set up an example graph and its matrix. Then we'll rank the members by direct influence, add two-step influence to break a tie, and finish with the reason a leader always exists in this kind of graph.

• How does a directed graph describe influence ?
• How does the adjacency matrix record the arrows ?
• How is dominance read from the matrix in one step ?
• How does the squared matrix count two-step influence ?
• How does adding both steps find a single dominant member ?
• Why does such a graph always have a member who reaches everyone in two steps ?

How does a directed graph describe influence ?

Before any matrix appears, we need to agree on what an arrow means. The same drawing can describe traffic flow, a food chain or a chain of command. So the meaning of an arrow comes from the situation, not from the graph itself.

The direction (arrow) in a Graph can be interpreted in many different ways depending on what kind of situation it is representing.

For example, the arrow can represents 'who influence who in a social network'. With this, following graph can be interpreted like this. The member v1 influence v3 and v4. The member v2 influence v1, v4, v5 etc.

The graph below has five members, v1 to v5, placed at the corners of a pentagon. Every pair of members is joined by exactly one arrow, so the graph carries 10 arrows in total. An arrow always points from the member who influences to the member who is influenced. Look at v4 in particular. All four of its arrows point inward, so v4 is influenced by everybody and influences nobody.

Figure 1. Influence graph of five members. Every pair of members is linked by one arrow, and v4 has no outgoing arrow.

• v1 influences two members : its arrows go to v3 and v4.
• v2 influences three members : its arrows go to v1, v4 and v5.
• v3 influences two members : its arrows go to v2 and v4.
• v4 influences nobody : the arrows from v1, v2, v3 and v5 all end at v4.
• v5 influences three members : its arrows go to v1, v3 and v4.

How does the adjacency matrix record the arrows ?

Counting arrows on a drawing works for five members, but it does not work for five hundred. The adjacency matrix turns the drawing into numbers that a computer can process. Every later step on this page is a matrix operation on it, so it is worth reading it carefully once.

The adjacent matrix for this matrix is represented as follows. (If you are not familiar with what Adjacent matrix is, refer to Adjacent Matrix page)

Row i of the matrix below belongs to member vi as the source of an arrow, and column j belongs to member vj as the target. The entry in row i, column j is 1 when an arrow runs from vi to vj. Otherwise it is 0. The diagonal is all zero, because no member has an arrow to itself.

Figure 2. Adjacency matrix A of the graph in Figure 1. A 1 in row i, column j means that vi influences vj.

• Row 2 reads 1 0 0 1 1 : v2 has arrows to v1, v4 and v5, which matches Figure 1.
• Row 4 is all zero : v4 influences nobody. Column 4 holds four 1s, because every other member influences v4.
• A is not symmetric : for each pair of members, exactly one of a_ij and a_ji is 1. So A + A^T has a 1 in every position off the diagonal.
• A row sum counts outgoing arrows : a column sum counts incoming arrows instead. Dominance is about influencing others, so it uses the row sums.

How is dominance read from the matrix in one step ?

Dominance represents 'who influence the most numbers of other members'. In case of directed graph, it can be identified by 'which vertices has the most numbers of outgoing arrows'.

Dominance among the members can be identified from Adjacent Matrix. You can figure out directly from adjacent matrix itself which vertex is Dominant one in single step.

For example, you can interpret the adjacent matrix as shown below. (In this case, v2 and v5 can be ranked as tie in terms of dominance).

The picture below writes the row sum of A beside each row. Each row sum is the number of outgoing arrows of that member. In graph terms it is the out-degree of the vertex.

Figure 3. One-step dominance from the row sums of A. v2 and v5 share the top score of 3, so one step does not give a single leader.

• The one-step ranking has a tie at the top : v2 and v5 score 3, v1 and v3 score 2, and v4 scores 0.
• The scores add up to the number of arrows : 2 + 3 + 2 + 0 + 3 = 10. Every arrow leaves exactly one member, so it is counted exactly once.
• The two leaders are not equal : v2 influences v5, but v5 does not influence v2. A plain row sum cannot see this difference. The next step uses exactly this kind of indirect link.

How does the squared matrix count two-step influence ?

Since we failed to find single dominant element from Adjacent matrix, we can check with the second step relationship by taking the power of 2 for the adjacent matrix. The result can be illustrated as follows.

Let's see why squaring the matrix helps. The entry in row i, column j of A² is the sum over k of a_ik a_kj. One term of that sum is 1 only when vi influences vk and vk influences vj. So the entry counts the two-step paths from vi to vj, and each path passes through one middle member vk. The picture below shows A² with the row sum of each row beside it.

Figure 4. Two-step influence from A². Member v2 has the most two-step paths, 5, and v5 follows with 4.

• Row 2 of A² is 1 0 2 2 0 : v2 reaches v1 through v5. It reaches v3 through v1 and through v5, and v4 through v1 and through v5. That is 5 paths.
• The row sum counts paths, not distinct members : the note beside row 2 says v2 influences 5 vertices in two steps. Those 5 paths reach only 3 distinct members, v1, v3 and v4, because a member reached by two routes is counted twice. Read the row sum as a weight of indirect influence rather than as a head count.
• The diagonal of A² is zero : a path vi to vk and back to vi would need arrows in both directions between vi and vk. This graph has only one arrow per pair, so no member influences itself in two steps.
• The same rule holds for any power : the entry in row i, column j of A^k counts the paths of exactly k steps from vi to vj.

How does adding both steps find a single dominant member ?

Adding A and A² gives each member one score for direct influence plus indirect influence through one middle member. Linear algebra textbooks that treat dominance in directed graphs call the row sum of A + A² the power of the vertex. Before you read the numbers, keep in mind that a direct arrow and a two-step path carry the same weight in this sum.

If you sum up both the first step dominance and the second step dominance, you will have the matrix as follows. From this matrix, you can identify a single, the most dominant member.

Figure 5. Combined one-step and two-step influence, A + A². Member v2 scores 8 and is the single dominant vertex, ahead of v5 with 7.

• The final ranking is v2, v5, v3, v1, v4 : the scores are 8, 7, 5, 4 and 0.
• Each score is the sum of two row sums : the row sum of A + A² equals the row sum of A plus the row sum of A². For v2 this is 3 + 5 = 8, and for v5 it is 3 + 4 = 7.
• The tie breaks on indirect influence : v2 influences v5 directly. So the members that v5 influences, v1, v3 and v4, are all two-step targets of v2 as well.
• You can weight the second step lower : if a direct arrow should count more, use the row sums of A + 0.5 A². The scores then become 3, 5.5, 3.5, 0 and 5, and v2 still leads.
• A tie can survive both steps : if two members still share the top score, add A³ as well. For this graph the row sums of A + A² + A³ are 7, 14, 10, 0 and 12, which keeps the same order.

Why does such a graph always have a member who reaches everyone in two steps ?

The graph in Figure 1 has a special structure, because every pair of members is linked by exactly one arrow. Graph theory calls such a graph a tournament, and linear algebra textbooks call it a dominance-directed graph. For this kind of graph a classic result holds. At least one vertex reaches every other vertex in one step or two steps.

The argument is short. Pick the member v with the largest one-step score. Suppose some other member u is not influenced by v directly. Then the single arrow between them points from u to v. Now suppose u is not reached in two steps either. Then u also beats every member that v beats, so u has at least one more outgoing arrow than v. That contradicts the choice of v. So the member with the highest one-step score always reaches everyone within two steps.

The table below checks this on the example. The last column counts distinct members reached in one or two steps, which is the number of nonzero entries in the row of A + A².

• Three members reach everyone here : v2, v3 and v5 all reach the other four members within two steps. The guarantee promises at least one, and this graph has three.
• A distinct count alone gives a three-way tie : the path count of A + A² is what separates v2 from v5 and v3.
• The guarantee needs one arrow per pair : in a general directed graph some pairs have no arrow, and then no member may reach everyone. The row sums of A + A² still rank the members, but the ranking no longer comes with this promise.
• v4 shows the other end of the ranking : a member with no outgoing arrow scores 0 at every power of A, because its row stays zero.