Communicability

graph-theory

Definition

Communicability

Communicability $C_{ij}$ is a measures the ease or efficiency with which information can travel from vertex $i$ to vertex $j$ through the graph.

It is defined as the matrix exponential of the adjacency matrix:

$$C=e^A=\sum _{k=0}^{\infty }\frac{A^k}{k!}=\underset{k\to \infty }{\lim }{\left(I+\frac{A}{k}\right)}^k$$

where:

• $e^A$ represents the number of walks of length $k$ between vertices

• $k!$ serves to weight walks of different lengths

  The element $C_{ij}$ is the total communicability between vertex $i$ and $j$, accounting for all possible walks of any length between them.

Understanding

The weighting factor $\frac{1}{k!}$ ensures that longer walks contribute less to communicability, reflecting that information is more likely to travel through shorter, more direct routes.