Kluged Curiosities and Network Connectivity, February 2016

While this blog has matured past the stamp-collecting phase of inquiry, we will nevertheless review a series of curiosities from the last few months. This includes a few readings from the network science literature that have been percolating (pardon the pun) through my reading queue.

The first of these is a game that relies on your pattern recognition skills as well as a keen eye for outliers. The "Guess the Correlation" game trains you to see the signal through the noise, provided that signal is a linear correlation amongst less than 100 datapoints.

Visual approximation of an embedded signal. COURTESY: guessthecorrelation.com

This is also a nice example of domain expertise versus the precision of statistical techniques [1], and perhaps a lesson in naive feature creation.

Crowdfunding, or raising modest amounts of money from large numbers of individuals, is emerging as an alternative way of raising money for side projects and attaining short-term research goals. A new paper on crowdfunding in PLoS Biology [2] called "A Guide to Scientific Crowdfunding" gives excellent tips for starting your own crowdfunding campaign and a bibliography for further reading on scientific crowdfunding.

Last year was the 55th anniversary marking the discovery of the giant component (a key foundation in the area we now call network science) by Erdos and Renyi [3]. Disrupting this giant component by reducing the connectivity of a complex network has many practical applications [4]. Kovacs and Barabasi [5] introduce us to the concept of connective destruction, which refers to the selective removal of nodes that partitions a network into smaller, disconnected components (effectively isolating subnetworks)?

Morone and Makse [6] attempt to solve this NP-hard problem by developing the collective influence algorithm. Collective influence takes into account a node's extended degree, or the degree of a central nodes as well as its connections up to several links away. By taking into account both the strong and weak links of a given node of high-degree, the computational complexity of optimal network partitioning can be reduced to O(n log n).

Explosive percolation, now officially famous. COURTESY: Allen Beattie and Nature Physics.

A related (and perhaps in some ways inverse) problem is that of explosive percolation. Explosive percolation is the sudden emergence of large-scale connectivity in networks [7]. As connective destruction makes it easier to control, say, a disease outbreak, explosive percolation makes it harder. Fortunately, we are discovering ways to control this transition [8]. For example, approaches based on Achlioptas processes (a form of competitive graph evolution) can be successful at delaying or otherwise controlling the onset of explosive percolation [9]. 

Recently, I got into a series of conversations about the use of Lena Soderberg's image as a standard computer vision benchmark. Apparently, one reason it is used is because it is the visual equivalent of a pangram [10]. Regardless, here is the historical background on one of the most benchmarked photos in Computer Science history [11].

The oft-benchmarked photo (circa 1972).

NOTES:
[1] Driscoll, M.E. The Data Science Debate: domain expertise or machine learning? Data Utopian blog. Accessed on 2/26/2016.

[2] Vachelard, J., Thaise Gambarra-Soares, T., Augustini, G., Riul, P., Maracaja-Coutinho, V. 2016. A Guide to Scientific Crowdfunding. PLoS Biology, 14(2), e1002373.

[3] Spencer, J. 2010. The Giant Component: the golden anniversary. Notices of the AMS, June/July, 720-724.

* discusses interesting historical links between discovery of the giant component and Galton-Watson processes (the mathematics of branching processes in biology).

[4] Kovacs, I.A. and Barabasi, A-L. 2015. Destruction perfected. Nature News and Views, 524, 38-39.

[5] Keeling, M.J. and Eames, K.T.D. 2005. Networks and epidemic models. Journal of the Royal Society Interface, 2(4), 295–307.

[6] Morone, F. and Makse, H.A. 2015. Influence maximization in complex networks through optimal percolation. Nature, 524, 65-68.

[7] Ouellette, J. 2015. The New Laws of Explosive Networks. Quanta Magazine, July 14.

[8] Achlioptas, D., D'Souza, R.M., and Spencer, J. 2009. Explosive Percolation in Random Networks. Science, 323(5920), 1453-1455.

[9] D'Souza, R.M. and Nagler, J. 2015. D'Souza, R.M. and Nagler, J. 2015. Anomalous critical and supercritical phenomena in explosive percolation. Nature Physics, 11, 531-538.

[10] A phrase that uses all of the letters in the available alphabet. One example: "the quick brown fox jumped over the lazy dog".

[11] Hutchinson, J. 2001. Culture, Communication, and an Information-Age Madonna. IEEE Professional Communication Society Newsletter, 45(3).