Simple set up
- Let $G=(V, E)$ be an undirected, unweighted, graph and let $A_G$ be the adjacency matrix of $G$. Is there a way to interpret the properties of the eigenvalues of $A_G$ to give insight about properties of $G$?
Complex set up
Now let $G=(V, E)$ be an undirected weighted graph where each edge, $(u, v)\in E$, has weight $w_{(u, v)}\in[0, 1]$. Let $A_G$ be the adjacency matrix of $G$. Consider the following setting, some set of nodes $S \subset V$ are chosen with $|S| = k$, for some $k$. These nodes are considered active. The active nodes then percolate activation through the graph in the following way. Each alive node, say $v$, attempts to activate each of its nonactive neighbors and succeeds with probability $w_{u, v}$, then all newly activated nodes attempt to active their neighbors, and so on. Each node may only attempt to active all its neighbors once during the entire process.
Is there some interpretation of how many nodes percolation will be able to activate based on properties of the eigenvalue of $A_G$?