Here is the abstract: “The study of networks has grown into a substantial interdisciplinary endeavor across the natural, social, and information sciences. Yet there have been very few attempts to investigate the interrelatedness of the different classes of networks studied by different disciplines. Here, we introduced a framework to establish a taxonomy of networks from various origins. The provision of this family tree not only helps understand the kinship of networks, but also facilitates the transfer of empirical analysis, theoretical modeling, and conceptual developments across disciplinary boundaries. The framework is based on probing the mesoscopic properties of networks, an important source of heterogeneity for their structure and function. Using our method, we computed a taxonomy for 752 individual networks and a separate taxonomy for 12 network classes. We also computed three within-class taxonomies for political, fungal, and financial networks, and found them to be insightful in each case.”
This summer in the Complex Systems Advanced Academic Workshop we are devoting attention to information theory. In collecting some materials about Claude Shannon, I came across the above video and thought I would share it with others. Here is the description … “Considered the founding father of the electronic communication age, Claude Shannon’s work ushered in the Digital Revolution. This fascinating program explores his life and the major influence his work had on today’s digital world through interviews with his friends and colleagues.”
Tomorrow is the first day of presentations at NetSci2010. Our paper will presented in AM Network Measures Panel. Anyway, for those interested in leveraging network science to study the dynamics of large social and physical systems — the conference promises a fantastic lineup of speakers. Check out the program!
From the article “… Vlatko Vedral, an Oxford physicist, examines the claim that bits of information are the universe’s basic units, and the universe as a whole is a giant quantum computer. He argues that all of reality can be explained if readers accept that information is at the root of everything.”
From the abstract: “There is a long standing debate over how to objectively compare the career achievements of professional athletes from different historical eras. Developing an objective approach will be of particular importance over the next decade as Major League Baseball (MLB) players from the “steroids era” become eligible for Hall of Fame induction. Here we address this issue, as well as the general problem of comparing statistics from distinct eras, by detrending the seasonal statistics of professional baseball players. We detrend player statistics by normalizing achievements to seasonal averages, which accounts for changes in relative player ability resulting from both exogenous and endogenous factors, such as talent dilution from expansion, equipment and training improvements, as well as performance enhancing drugs (PED). In this paper we compare the probability density function (pdf) of detrended career statistics to the pdf of raw career statistics for five statistical categories — hits (H), home runs (HR), runs batted in (RBI), wins (W) and strikeouts (K) — over the 90-year period 1920-2009. We find that the functional form of these pdfs are stationary under detrending. This stationarity implies that the statistical regularity observed in the right-skewed distributions for longevity and success in professional baseball arises from both the wide range of intrinsic talent among athletes and the underlying nature of competition. Using this simple detrending technique, we examine the top 50 all-time careers for H, HR, RBI, W and K. We fit the pdfs for career success by the Gamma distribution in order to calculate objective benchmarks based on extreme statistics which can be used for the identification of extraordinary careers.”
The model is a fairly simple discrete-time directed growing graph. At time 0, we create a completely disconnected graph with some initial number of vertices. The number of new vertices after time 0 is then modeled by a homogeneous Poisson process. For each of these new vertices, we also model the number of edges per vertex as IID Poisson distributions. The probability distribution over these edges is specified by a modified preferential attachment mechanism.
Most of our questions consider what we’ve called theaverage pairwise stability. This can be thought of as answering the following question: “what is the probability that Alice and Bob are friends tomorrow if they were friends today?” Here, friendship corresponds to sharing the same community. By asking this question for all pairs of vertices (dyads) for all time steps in which both vertices existed, we get a probability that a community dyad is preserved from step to step. It is important to note that we’re not claiming all algorithms applied to all systems should have high average pairwise stability.In fact, for systems that involve dynamics like random rewiring, the only way to get high pairwise stability is to put all vertices in the same community or their own community at all steps – obviously trivial and unhelpful solutions in practice.
Given this model and this conception of stability, we want to perform the following experiments:
How do the edge-betweenness, fast greedy, and leading eigenvector community detection algorithms compare in terms of their average pairwise stability…
for varying levels of preferential attachment?
for varying vertex and edge rates?
Is there a significant tradeoff between the number of communities and the average pairwise stability of these community detection algorithms?
The answers are yes, yes, and yes! You shouldread the paper for more details.
I’ve also produced some code to help you assess the average pairwise stability for your dataset. The code requires igraph and is only in Python at this point due to an issue with R’s vertex label handling (which I can hopefully work around). You canget the average pairwise stability methods on github and check out the example below:
From the Abstract … “The race is on to build a computer that exploits quantum mechanics. Such a machine could solve problems in physics, mathematics and cryptography that were once thought intractable, revolutionizing information technology and illuminating the foundations of physics. But when?” (Subscription may be required for Access)
