4
$\begingroup$

I am wondering if someone knows how to compare two directed network graphs with the same node IDs.

Specifically, in graph A, each node represents an individual, and each edge represents some sort of relationship A between two individuals. In graph B, the same population is represented by the nodes, and each edge represents a relationship B between two individuals.

How should I test for significant difference between these two graphs? Both graphs are directed. What if the graphs are weighted?

I am currently using igraph in R, but am looking for more of a statistical answer.

Thanks so much!

Improve this question
$\endgroup$
1
  • $\begingroup$ No statistical answer is possible without some probability model for how such graphs might naturally vary. What is your model? $\endgroup$ – whuber♦ Jan 24 '14 at 21:06
3
$\begingroup$

Testing for significance means first defining what classes of results are considered "more surprising" and "less surprising." In 1D normally-distributed statistical tests, results near the mean are less surprising than the empirical result, and the p-value is defined as the area under the curve where the result is more surprising than the emprical result.

Once you define what types of graph-differences are most surprising, you can do some monte carlo simulation of graphs and count how many of them fit that description.

Along the way you'll have to make some assumptions specific to your specific model. Don't expect an out-of-the-box procedure for this kind of thing.

Personally I would start by making an adjacency matrix, computing the eigens, then maybe computing the angle between the principal eigenvector of A and that of B. Then do some Monte-Carlo-simulated matrices based on your null-hypothesis data model, and see how many of them have a larger angle than the empirical one. Adjust this procedure as you need.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1: "...based on your null-hypothesis data model" is a nice way to provide a general yet useful answer. $\endgroup$ – whuber♦ Jan 24 '14 at 22:12
3
$\begingroup$

Leonardi (2007) uses the Quadratic Assignment Procedure - QAP (Hubert & Schultz, 1976), which has also been developed further by Krackhardt (1987).

What QAP does is that it essentially takes the adjacency matrices of the two graphs that you are comparing, and then calculates Pearson correlation coefficients for each pair of matched cells (for the same set of nodes) in each adjacency matrix. It then permutes the mappings of potential edges between nodes to generate a sampling distribution, of sorts, which enables us to test for significant correlations for structural relationships.

This yields a correlation between the two graphs as wholes, with a significance value attached to it - thus enabling you to evaluate to what degree to graphs are correlated (in terms of their structure), and whether that correlation is significantly different from zero.

References

Hubert, L., and Schultz, J. 1976. “QUADRATIC ASSIGNMENT AS A GENERAL DATA ANALYSIS STRATEGY,” British Journal of Mathematical and Statistical Psychology (29:2), pp. 190–241.

Krackardt, D. 1987. “QAP Partialling as a Test of Spuriousness,” Social Networks (9), pp. 171–186.

Leonardi, P. 2007. “Activating the Informational Capabilities of Information Technology for Organizational Change,” Organization Science (18:5).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Your answer is interesting for me. What do you mean by " potential edges ", do you mean the existing edges? $\endgroup$ – M.M Feb 10 '14 at 14:43
  • $\begingroup$ Potential edges are all the relationships which could exist, out of which only a few can actually be found in the empirical data. $\endgroup$ – histelheim Feb 10 '14 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.