Learning from
success & failure:
Using graph spectra to identify
differences in network structure
Matt Michalska-Smith
- Stefano Allesina
- Jacopo Grilli
The Question:
Is it possible to distinguish networks of differing types by their structure?
- Interaction Type:
- the real-world-event being depicted by a network link
- Network Structure:
- the arrangement of connections within a network
Previous Attempt:
- Many (> 300) biological networks
- Vast diversity of type and structure
- Many (36) metrics of structure for each network
- – Each compared to two distributions from randomized networks
- Principal Component Analysis
$\Rightarrow$ No discernable clustering
Reassessment
Method $\Leftrightarrow$ Data
Method
$$B_{ij} = \{0,1\}$$
$$B_{ij}^{(ER)} = \mathcal{B}(1, C)$$
$$B_{ij}^{(CM)} = d_id_j / L$$
Where $d_i$ is the degree of node $i$, L is the number of links in the network, and $C = L / (nm)$, with $n$, $m$ being the number of rows, columns respectively
$$\scriptsize \lambda_1^{(ER)} = \left(\mathbb{E}[d_r] + \frac{(m - 1) C_r (1 - C_r)}{\mathbb{E}[d_r]}\right) \left(\mathbb{E}[d_c] + \frac{(n - 1) C_c (1 - C_c)}{\mathbb{E}[d_c]}\right)$$
$$\scriptsize \lambda_1^{(CM)} = \frac{\mathbb{E}[d_c^2]}{\mathbb{E}[d_c]} \frac{\mathbb{E}[d_r^2]}{\mathbb{E}[d_r]}$$
Where $d_r$, $d_c$ are vectors of the row, column node degrees respectively, and $C_r$, $C_c$ are connectance values corrected for the constraint of a connected network
Taking the ratio of the empirically observed $\lambda_1$ to these expectations allows us to "account" for less informative variation.
Data
Current Attempt
- Very many (> 2000) nonbiological networks
- Less diversity of type and structure
- – Especially within network types
- Few (2-6) metrics of structure for each network
- Principal Component Analysis (?)
Some more things to do...
- More Biological Data
- – Genetics?
- Additional metrics?
- – $\mathbb{E}[\lambda_1]$ for random graphs with additional constraints?
Thank you!
