CSE 2013: Large-scale Network Analysis at SIAM CSE Conference

June 3, 2013

BTER graph model. The nodes are color-coded---darker nodes are of higher degree. The blue edges correspond to affinity blocks, and the green edges to “random” connections. Image by Nurcan Durak, courtesy of Tamara Kolda.
Tamara G. Kolda and Ali Pinar

The organizers of the 2013 SIAM Conference on Computational Science and Engineering chose "Scalable Algorithms for Big Data" as one of the main conference themes. We can better understand many real-world data sets by looking at their connectivity (i.e., the network or graph) rather than at static features. The early success of Google's PageRank analysis, for instance, showed that incorporating connectivity in web search was much more effective than keyword analysis alone. Today, network analysis plays an important role in a wide variety of application domains, including biology, chemistry, economy, communications, transportation systems, cybersecurity, sociology, and even sports analysis.

Large-scale networks are ubiquitous: Consider social networks; graphs of links between web pages; the power grid; graphs of phone, e-mail, or text communications; graphs of purchasing and/or financial transactions; player interaction networks in multiplayer online games; and computer network traffic between various IP addresses. These networks are not described simply by nodes and edges, but by attributed graphs, whose nodes and edges carry (possibly changing) properties. Moreover, the edges may have both timestamps and directionality, which appears (and disappears) based on the interactions between nodes.

The size of such networks is already quite large. For instance, public data sets available for research have graphs as large as 100 million nodes and 4.5 billion edges, and these are tiny compared to many graphs that companies like Facebook and Google are analyzing. Moreover, these data sets continue to grow in size---far outstripping analysis capabilities.

Several talks at CSE13 focused on ways to handle these large, complex, and evolving data sets. The challenges ranged from the theoretical (e.g., generating uniformly random instances of graphs) to the practical (e.g., discovering computer malware) and everything in between. Here are a few highlights:

CSE13 was remarkable for demonstrating both the growing importance of network analysis itself and the role of applied mathematics within network analysis.

Tamara G. Kolda and Ali Pinar are Members of the Technical Staff at Sandia National Laboratories in Livermore, California.

Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy's National Nuclear Security Administration under contract DE-AC04-94AL85000.

Renew SIAM · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube