Archive for the ‘Scale-Free’ Category

Evidence for Power Laws – “…I work scientifically!”

Saturday, February 17th, 2018

Scant Evidence of Power Laws Found in Real-World Networks by Erica Klarreich.

From the post:

A paper posted online last month has reignited a debate about one of the oldest, most startling claims in the modern era of network science: the proposition that most complex networks in the real world — from the World Wide Web to interacting proteins in a cell — are “scale-free.” Roughly speaking, that means that a few of their nodes should have many more connections than others, following a mathematical formula called a power law, so that there’s no one scale that characterizes the network.

Purely random networks do not obey power laws, so when the early proponents of the scale-free paradigm started seeing power laws in real-world networks in the late 1990s, they viewed them as evidence of a universal organizing principle underlying the formation of these diverse networks. The architecture of scale-freeness, researchers argued, could provide insight into fundamental questions such as how likely a virus is to cause an epidemic, or how easily hackers can disable a network.

An informative and highly entertaining read that reminds me of an exchange between in The Never Ending Story between Atreyu and Engywook.

Engywook’s “scientific specie-ality” is the Southern Oracle. From the transcript:

Atreyu: Have you ever been to the Southern Oracle?

Engywook: Eh… what do YOU think? I work scientifically!

In the context of the movie, Engywook’s answer is deeply ambiguous.

Where do you land on the power law question?

Uncovering disassortativity in large scale-free networks

Friday, June 22nd, 2012

Uncovering disassortativity in large scale-free networks by Nelly Litvak and Remco van der Hofstad.


Mixing patterns in large self-organizing networks, such as the Internet, the World Wide Web, social and biological networks are often characterized by degree-degree {dependencies} between neighbouring nodes. In this paper we propose a new way of measuring degree-degree {dependencies}. We show that the commonly used assortativity coefficient significantly underestimates the magnitude of {dependencies}, especially in large disassortative networks. We mathematically explain this phenomenon and validate the results on synthetic graphs and real-world network data. As an alternative, we suggest to use rank correlation measures such as the well-known Spearman’s rho. Our experiments convincingly show that Spearman’s rho produces consistent values in graphs of different sizes but similar structure, and it is able to reveal strong (positive or negative) {dependencies} in large graphs. In particular, using the Spearman’s rho we show that preferential attachment model exhibits significant negative degree-degree {dependencies}. We also discover much stronger negative {degree-degree dependencies} in Web graphs than was previously thought. We conclude that rank correlations provide a suitable and informative method for uncovering network mixing patterns.

If you are using graphs/networks and your analysis relies on dependencies between nodes, this could be of interest.

Graphs that involve large numbers of nodes in terrorism analysis, for example.

Being mindful that one person’s “terrorist” is another person’s defender of the homeland.