Monday, November 7, 2011

Quotes from network analysis papers

I'm currently doing a heavy literature research in network analysis and from time to time I find quotes that need some more audience.


"We use the term reciprocity  to depict the degree of mutuality of a relationship. A re-
lationship with a high reciprocity is one where both are equally interested in keeping up
the relationship — a good example is the relationship of Romeo and Juliet in the famous
play with the same name by William Shakespeare, where the two lovers strive to share each
other’s company despite their families’ objections. On the other hand, in a relationship with
a low reciprocity one person is significantly more active in maintaining the relationship than
1the other. We judge reciprocity from actual communications taking place between people.

In Shakespeare’s time this would have meant counting the number of poems passed and
sonnets sung, but in our modern era it is easier to make use of the prevalence of electronic
communication." :-) [Lauri Kovanen, Jari Saramäki, Kimmo Kaski: "Reciprocity of mobile phone calls", ArXiv:1002.0763v1 [physics.soc-ph], p. 1-2]

Centrality Indices

Sabidussi about the introduction of new centrality indices:
"There is no doubt that an appeal to intuition must be made at some level, but it has to be made in a mathematically precise fashion." (Sabidussi, The centrality index of a graph, Psychometrika 31(4), 581-603, 1966)
So, how good is your mathematical precision on your intuition? ;-)

Sabidussi tried an axiomatic approach to centrality indices. He required for example that adding an edge to the most central vertex of a graph should always result in a graph in which the same vertex is still most central. Although this sounds intuitive, most centrality indices do not stand this test (e.g., eccentricity). Nonetheless, Sabidussi concludes:

"One may, of course, blame this wholesale failure on our axiom system.There is little doubt, however, that the three indices [which he tested and which failed as well, among them a closeness-type of centrality] [...] would not survive even a more sophisticated system of axioms. In view of this, we strongly suggest that [these measures] be discarded and that centrality be measured by the trivial index [1/(n - degree of the node)] defined [above]. [It] is more easily calculated than any of the other indices, and, whatever its intuitive shortcomings, it has the decided advantage of satisfying a well-defined system of axioms." Sabidussi, 1966 (p. 20, see above)

Citation Failures

As everyone knows and thankfully remarked by Goh, Kahn and Kim [Universal Load of Load Distribution in Scale-Free Networks, PRL, 87(27), 278701, 2001], Mark Newman introduced the BFS: "... and measure the load along the shortest path using the modified version of the breath-first  [sic!] search algorithm introduced by Newman [ M. E. J.  Newman,  Phys.  Rev.  E  64,  016131  (2001);  64, 016132 (2001)] "

Excuses and Justifications

"Edge weights in networks have, with some exceptions [...], received relatively little attention in
the physics literature for the excellent reason that in any field one is well advised to look at the simple cases first (unweighted networks) before moving on to more complex ones (weighted networks). " M.E.J. Newman, "Analysis of weighted networks", ArXiv:cond-mat/0407503v1

Excuse for not asking all participants of the study the same questions:
"We only asked the last two informants this question because it didn't occur to us earlier."  
 [Bernard, H. R.; Shelley, G. A. & Killworth, P.: "How much of a network does the GSS and RSW dredge up? Social Networks, 1987, 9, 49-61]
In general I have the feeling that scientific articles were more personal in these days. This particular article is started with the following quote:  "At my twenty-fifth high school reunion, last year, you would have been proud of me. They way i called those names up, with seldom a quick half glance at a tag ... their names came to me like the list of vowels, because I had learned them when i was fresh, back before I had met or heard of 375,000 other Americans. By the time anyone gets to be 43, if he has followed current events and been out of town a few times, two thirds of the names he hears sound vaguely, but only vaguely, familiar" (From "Not exactly what I had in Mind", Roy Blount Jr., The Atlantic Monthly Press, 1985)
I wish we would read more of the persons behind research. It would remind us all that science is quantifiable but still conducted by humans which err or make subjective decisions.

The following is a quote by two physicists about their engagement in economy, but the statement seems so general that it might fit to network analysis as well:
"Physicists are not, however, accustomed to waiting for a fully formed theory before reporting new results." Tobias Preis and H. Eugene Stanley: "Bubble trouble", Physics World May, p. 29-32, 2011.

Data quality: Protein-protein interaction networks

Mackay et al. wrote a paper about protein-interaction data and how bad they are. They have tried to re-produce around 20 published protein-protein interaction pairs but were only able to reproduce less than half. Their article starts with the following sentences:

"When Othello concluded, on the basis of flimsy evidence, that Desdemona had indulged in inappropriate physical interactions, great tragedy ensued. We believe that many reported protein interactions are similarly based on insufficient data, and therefore risk skewing the literature."
(Mackay, J. P.; Sunde, M.; Lowry, J. A.; Crossley, M. & Matthews, J. M. Protein interactions: is seeing believing? TRENDS in Biochemical Sciences, 2008, 32, 530-531)

I really wonder whether we want to base any type of network analysis where up to 50% of all edges are false-positive.

Copy-pasting story lines

  There are some story lines in network analysis I just have heard way too often and it seems they are just copy-pasted from one paper to the other. One of them is: "Until recently, network modeling often assumed the topology  was  either  a  random  graph  or  a  regular  lattice." In this case, that is a citation from Goldberg and Roth, "Assessing experimentally derived interactions in a small world", PNAS 100(8), p. 4372-76, 2003, but actually it can be found in slight variations in hundreds of papers. It is a very interesting topic in itself, how science builds narratives that convey their beliefs in a model but I think it is important to stop from time to time and re-think a story line. Often, the narrative becomes oversimplified by little "mutations" along their copy-and-paste evolution that essentially hinders science more than helps it. Coming back to the example: It is unreasonable that any mature scientist would actually assume that a real world network was either a random graph or a regular lattice. We have modeled it as a random graph or a regular lattice in the hope that these models capture the essential properties of it - or just because a random graph model and a lattice comes in handy when trying to calculate things. The origins of these two models, especially in complex network analysis, is that atomic interactions in cristal lattices could be analyzed and solved in exactly two models: a lattice structure, which comes natural for cristals, or in a random graph fashion - which is not a natural choice but one in which some insight into the model can be gained. Thus, in the paper of Watts and Strogatz, which both come from statistical physics in which these interactions are an important research question, they focused on these two models - they were prevalent in statistical physics and well understood there. It is thus reasonable to transfer these models to real-world interaction between other things than atoms just to see how well they do. This has nothing to do with actually assuming that the models capture the real-world interactions in any meaningful way.

Mathematical modeling (in general and for network analysis)

In his article Sampling in social networks, Rothenberg cites Rapoportas follows: "Mathematical modeling is a vehicle for absolutely rigorous reasoning and therein lies its advantage. A disadvantage of mathematical modeling is that it necessitates a drastic paring down of the details of the phenomena modeled...these simplifications...can impair or altogether destroy the model's pragmatic relevance."

To be continued...