of a network in terms of local structural features. In Section \[Optimal Bounds\], we use convex optimization to derive optimal bounds on the smallest (and largest) eigenvalue of the interaction network from these moments. Our bounds help us to understand how structural properties of a network impact the stability properties of the Nash equilibria in the game. We illustrate our results with numerical simulations in real online social networks in Section \[Simulations\].

Notation
--------

Let $\mathcal{G}=\left( \mathcal{V},\mathcal{E}\right) $ denote an undirected graph with $n$ nodes, $e$ edges, and no self-loops[^3]. We denote by $\mathcal{V}\left( \mathcal{G}\right) =\left\{ v_{1},\dots
,v_{n}\right\} $ the set of nodes and by $\mathcal{E}\left( \mathcal{G}%
\right) \subseteq \mathcal{V}\left( \mathcal{G}\right) \times \mathcal{V}%
\left( \mathcal{G}\right) $ the set of undirected edges of $\mathcal{G}$. If $\left\{ v_{i},v_{j}\right\} \in \mathcal{E}\left( \mathcal{G}\right) $ we call nodes $v_{i}$ and $v_{j}$ *adjacent* (or neighbors), which we denote by $v_{i}\sim v_{j}$ and define the set of neighbors of $v_{i}$ as $%
\mathcal{N}_{i}=\{w\in \mathcal{V}\left( \mathcal{G}\right) :\left\{
v_{i},w\right\} \in \mathcal{E}\left( \mathcal{G}\right) \}$. The number of neighbors of $v_{i}$ is called the *degree* of the node, denoted by $%
d_{i}$. We define a *walk* of length $k$ from $v_{0}$ to $v_{k}$ to be an ordered sequence of nodes $\left( 