Sandberg’s Talk
What follows is a review of Network Mathematics: Why is it a Small World?, a talk given by Oskar Sandberg at Defcon 15.
One thing that is good to keep in mind is Sandberg’s point about the fact that the study of graphs is, by virtue of their applicability to a wide set of data, interdisciplinary in scope.
One thing I loved about the presentation was his visualization of the 200 node random graph with varying p (where p is the probability of two nodes having an edge during random graph creation). Notably, with small p, the paths possible between nodes were very disconnected, and many nodes were isolated without any edges at all.
However, when p > 1/n , the result was a large connected cluster, where most nodes were connected, and most were in a single large cluster. The illustration really drove that home when you see the entire graph become a single color. He makes a valuable point, I think, in using this property of random graphs to explain the resilience to attacks in random networks.
Further, when p > log(n)/n , we end up with a single connected cluster where all nodes are covered. This was a good illustration of the phenomenon that Albert and Barabási talked about where at some p, a sudden change takes place in the random graph and this property suddenly comes into being.
He also gives a name, “preferential attachment” to Albert and Barabási’s skewed degree distributions (relating to the power law degree distributions talked about in my last post).
Talks about Kleinberg’s work on searching the network. According to Sandberg, Kleinberg’s model attempts to condition the probability of edge formation in the random graph based on node similarity (for instance, euclidean distance). So, given an edge e = {u,v} and a distance d(u,v), the probability of an edge forming between vertices u and v, or P(e), is equal to the inverse of the distance raised to a power, which he calls alpha. Kleinberg found that the only case where the network is searchable occurs when alpha is 2 (for two dimensions). So, alpha “tunes” the locality of the shortest paths in the network.
Using that finding as a foundation, Sandberg models the generation of networks that allow searching by conditioning the probability with respect to the similarity between nodes. In other words, he increases the likelihood of edge creation for nodes with lower distance between them, in addition to another similarity metric besides distance. He illustrates this by combining euclidean distance with node similarity (modeling similarity with RBG color distance between colored vertices).
So, his network creation algorithm uses a greedy search across euclidean distance, adding edges to encountered nodes based on if the newly encountered node has the most similar color to the source node thus far. He uses this color difference as a proxy for determining “spaces of interest” in order to influence his model.
The talk highlights one property of the graph that is perhaps most interesting, the power law distribution of the resultant edges is what enables the searchability aspect (tractably finding a short path between any two nodes) of the overall graph.