SIAM Computational Science and Engineering (CSE) 2017
Atlanta, Georgia, USA
27 February  2 March 2017
Table of Contents
1 Modeling and Computational Methods in Network Science and Applications
Monday, 27 February 2017
In recent years, there has been high demand for novel and accurate mathematical models, and fast, stable and scalable computational techniques to address problems emerging from applications on realworld networks, such as social media and power grids. In these applications, big data is often generated, collected, stored and/or processed in largescale heterogeneous networks. New models and computational methods must tackle challenges of inhomogeneous structures of networks, randomness of dynamics, and noise in data. This minisymposium focuses on the recent advances of mathematical modeling and numerical methods as well as their applications in modern network science.
Organizers:
 Xiaojing Ye, Georgia State University
 Hongyuan Zha, Georgia Institute of Technology
 Haomin Zhou, Georgia Institute of Technology
Talks:
 MS7
 Influence Prediction for ContinuousTime Information Propagation on Networks Using GraphBased FokkerPlanck Equation

Xiaojing Ye, Georgia State University
We consider the problem of predicting influence, defined as the expected number of infected nodes, resulted from information propagating from any given set of source nodes on a network. We develop a novel and transformative framework that adaptively aggregates the activation states of the network according to the number of active nodes, leading to the construction of a system of differential equations that governs the time evolution of the state probabilities. This system is analogous to the FokkerPlanck equation in continuous space, and the solution readily yields the desired influence. This approach gives rise to a class of novel and scalable algorithms that work effectively for largescale and dense networks. Numerical results on a variety of synthetic and realworld networks will be presented.
 WalkBased Centrality and Communicability Measures: Algorithms and Applications

Michele Benzi, Emory University
In this talk I will review some network centrality and communicability measures based on walks. These measures can be given an elegant closed form in terms of functions of the adjacency matrix. I will introduce the notion of total communicability of a network as a measure of network connectivity and robustness and show that it can be computed very quickly even for large graphs. Finally, I will discuss efficient edge modification strategies (including edge removal, addition, and rewiring) that can be used to obtain networks with desirable communicability properties.
The talk is based on recent work in collaboration with Christine Klymko (LLNL) and Francesca Arrigo (Strathclyde).
 Enhanced Community Detection in Multilayer and Temporal Networks through Layer Aggregation

Dane Taylor, University of North Carolina at Chapel Hill; Rajmonda Caceres, Massachusetts Institute of Technology; Peter J. Mucha, University of North Carolina at Chapel Hill
Inspired by realworld networks consisting of layers that encode different types of connections, such as a social network at different instances in time, we study community structure in multilayer networks. We analyze fundamental limitations on the detectability of communities by developing random matrix theory for the dominant eigenvectors of modularity matrices that encode an aggregation of network layers. Aggregation is often beneficial when the layers are correlated, and it represents a crucial step for the discretization of timevarying network data, whereby layers are binned into time windows. We explore two methods for aggregation: summing the layers’ adjacency matrices as well as thresholding this summation at some value. We analyze detectability phase transitions that are onset by varying either the density of withincommunity edges or community size. We identify layeraggregation strategies that are optimal in that they minimize the detectability limit. Our results indicate good practices in the context of community detection for how to aggregate network layers, threshold pairwiseinteraction data matrices, and discretize timevarying network data. We apply these results to synthetic and empirical networks, including a study of anomaly detection for the Enron email corpus.
 Dynamic Processes Over Information Networks: Representation, Modeling, Learning and Inference

Le Song, Georgia Institute of Technology
Largescale and high resolution data from dynamic processes over networks are becoming increasing available nowadays from online social platforms, such as Twitter and Facebook. Such data provide great opportunities for understanding and modeling both macroscopic (network level) and microscopic (nodelevel) patterns in human dynamics. Such data have also fueled the increasing efforts on developing methods to address the challenges arising from understanding, predicting, controlling and distilling knowledge from these dynamic processes over networks, and answer query such as "who will do what and when?" To tackle these challenges, I will present a framework based on point processes for representing and modeling such data, and performing learning, inference and control over dynamic processes over networks.
 MS36
 Social Networks as Point Processes

Martin Short, Georgia Institute of Technology
The study of social networks, and the dynamics of activity taking place on those networks, is currently of great interest, thanks in part to the availability of datasets from sources such as Facebook and Twitter. In this talk, I will discuss networks in the context of the dynamics of events occurring within them, referencing two seemingly very different applications: a network of gang rivalries from Los Angeles and a network of email activity among a small group of college students. I will describe how both of these datasets can be understood through a common mathematical framework, the selfexciting point process. This modeling framework allows us to study interesting and difficult questions regarding the data, such as: which gangs were involved in a given violent altercation, and how might one infer "leadership" of a social network by studying the underlying dynamics?
 RealTime InSitu Seismic Imaging with Sensor Networks

WenZhan Song, University of Georgia
The seismic imaging process today involves massive seismic data collection from hundreds and thousands of seismic sensors to a central place for post computing. The whole process is expensive and often takes days even months to complete. There is great demand for realtime as it would reduce the costs and risks of E&P and mitigate the environment concerns. This talk presents an innovative Realtime Insitu Seismic Imaging (RISI) system that computes and visualizes the 3D subsurface imaging in seconds. The RISI system is a mesh network that sense and process seismic signals, and compute 3D subsurface image insitu in realtime. Instead of data collection then post processing, the mesh network performs the distributed data processing and inversion computing under the severe bandwidth and resource constraints, and generates an evolving 3D subsurface image as more events arrive. Several innovative distributed seismic imaging algorithms have been successfully developed and validated using both synthetic and realworld seismic data set. The hardware prototype system has also been implemented and can be extended as a general field instrumentation platform, to incorporate new geophysical data processing and computing algorithms, beyond seismic.
 Abnormal Synchrony in Evolving Brain Networks

Igor Belykh, Reimbay Reimbayev, and Kevin Daley, Georgia State University
This talk addresses a fundamental question of how pathological synchronized rhythms, associated with epileptic seizures and Parkinson’s tremors, appear in brain networks as a result of complex spatial and temporal dynamics of the brain network. There is experimental evidence showing that evolving brain networks change their functional structure during epileptic seizures from a more regular to a more random structure. In this talk, we will discuss the role of evolving network structure and the switching between healthy and abnormal rhythms that is accompanied by a change in intrinsic dynamics of neurons.
2 HighPerformance Graph Algorithms
Tuesday, 28 February 2017
Graph algorithms play an important role in the manipulation, distribution and analysis of large data sets arising from both traditional and emerging computational science applications. This minisymposium brings together researchers engaged in developing highperformance parallel graph algorithms with applications to parallel computing, linear system solvers, genomics, neuroscience, and cybersecurity.
Organizers:
 Karen D. Devine, Sandia National Laboratories
 Kamesh Madduri, Pennsylvania State University
 Siva Rajamanickam, Sandia National Laboratories
Talks:
 MS103
 Maintaining Connected Components for Infinite Graph Streams

Jonathan Berry, Sandia National Laboratories; Matthew Oster, Pacific Northwest National Laboratory; Cynthia Phillips, Steve Plimpton, and Timothy Shead, Sandia National Laboratories
We present an algorithm to maintain the connected components of a graph that arrives as an infinite stream of edges. Connectivityrelated queries, including component spanning trees, are supported with some latency, returning the state of the graph at the time of the query. Because an infinite stream may eventually exceed the storage limits of any number of finitememory processors, we assume an aging command or daemon where “uninteresting” edges are removed when the system nears capacity. Following an aging command the system will block queries until its data structures are repaired, but edges will continue to be accepted from the stream, never dropped. The algorithm will not fail unless a modelspecific constant fraction of the aggregate memory across all processors is full. In normal operation, it will not fail unless aggregate memory is completely full.
Unlike previous theoretical streaming models designed for finite graphs that assume a single shared memory machine or require arbitrarysize intermediate files, we distribute a graph over a ring network of finitememory processors. We implemented our algorithm using an asynchronous messagepassing system. We sketch the algorithm and give preliminary experimental results on synthetic and real graph streams.
 Updating Dynamic Networks in Parallel Using Graph Sparsification

Sanjukta Bhowmick and Sriram Srinivasan, University of Nebraska, Omaha; Sajal Das, Missouri University of Science and Technology
We present graph sparsification, an elegant technique for updating the properties of dynamic networks. Using graph sparsification the original network is divided into several small subgraphs. Each subgraph contains a set of specially marked edges, known as key edges, that pertain to the property to be updated. Each addition/deletion of edges is updated with respect to these key edges. In our presentation, we will show how by using graph sparsification we can develop scalable algorithms to update properties of weighted graphs such as minimum spanning tree and single source shortest paths.
 Computing Graph Centrality

Erik Saule, University of North Carolina, Charlotte; A. Erdem Sariyüce, Sandia National Laboratories; Kamer Kaya, Sabanci University, Turkey; Ümit V. Çatalyürek, Georgia Institute of Technology
Computing the centrality of a graph is a useful tool for many applications ranging from social network to traffic analysis, from drug discovery to urban planning. While many definitions of centrality exists, the most commonly used – namely betweenness and closeness centrality – are variations on the theme of allpair shortest path. With a complexity of O(V E )O(VE), computing centrality is difficult in practice; computing centralities efficiently has attracted quite some interest in the recent years.
In this talk, we will review the techniques one has to deploy to reach the highest performance when computing graph centrality. In both case of static graphs and incremental graphs, we will show that computing centrality on modern computing system involves both algorithmic and system issues.
 HighPerformance Graph Traversal for De Bruijn GraphBased Metagenome Assembly

Vasudevan Rengasamy and Kamesh Madduri, Pennsylvania State University
De Bruijn graphbased assembly is a popular technique for analyzing modern genomic and metagenomic DNA sequencing data. This technique is comprised of several computational building blocks, with the ultimate goal of reconstructing genomes based on overlapping shorter strings. This work describes new scalable, parallel implementations of several key compute and memoryintensive steps of the De Bruijn graphbased assembly technique. We focus on exploiting multicore parallelism and parallel I/O capabilities available on current supercomputers, and also target memory efficiency, i.e., fully inmemory execution using as few compute nodes as possible. We demonstrate applicability of these optimized implementations by integrating them with the MEGAHIT metagenome assemble.
 MS130
 Balanced MultiCriteria Graph Partitioning

Cedric Chevalier and Remi Barat, CEA/DAM, France; Francois Pellegrini, University of Bordeaux, France
Multicriteria graph partitioning is a key component for enabling highly scalable multiphysics simulations. The main challenge is to balance all the criteria at the same time. Existent multicriteria partitioners such as ParMetis are adapted from monocriterion and focus their goal in minimizing communication cost. However, in practice, this approach is not robust in respect to balance of all criteria, often producing results that are not in the imbalance tolerance.
We have implemented, in Scotch, specific multicriteria partitioning algorithms, designed to meet balance constraints for all criteria. In this talk, we will present and discuss results of these new algorithms.
 Multilevel Acyclic Partitioning of Directed Acyclic Graphs for Enhancing Data Locality

Julien Herrmann, Georgia Institute of Technology; Aravind Sukumaran Rajam, Ohio University; Fabrice Rastello, Inria, France; P. (Saday) Sadayappan, Ohio State University; Ümit V. Çatalyürek, Georgia Institute of Technology
In modern computational systems, the cost of data movement across nodes or within the memory hierarchies inside a node becomes more and more significant over the cost of performing arithmetic operations. When executing a program, maximizing data reuse will reduce the data movement cost and thus, improve the general execution time. Finding a good acyclic partition of the computational directed acyclic graph (DAG) associated with the algorithm can help finding an execution improving data locality. We present a multilevel direct kway partitioner for the acyclic partitioning of DAGs. The quality of the computed acyclic partitions are assessed at the graph level by computing the edge cut or the total volume of communication between components, and at the application level by computing the number of cache miss introduced by the partition on various algorithms.
 Partitioning Irregular Graphs at the TrillionEdge Scale

George M. Slota, Rensselaer Polytechnic Institute; Siva Rajamanickam, Sandia National Laboratories; Kamesh Madduri, Pennsylvania State University; Karen D. Devine, Sandia National Laboratories
We introduce XtraPuLP, a new distributedmemory partitioner designed to scale to trillionedge graphs. XtraPuLP is a significant extension from our prior sharedmemory partitioner, PuLP, and is based on the label propagation community detection technique. Label propagation has been previously demonstrated to be an effective means of partitioning modern extremescale graphstructured datasets, including human social and interaction networks, web craws, and brain graphs. On a collection of large sparse graphs, we show that XtraPuLP partitioning quality is comparable to other stateoftheart partitioning methods. We also demonstrate that XtraPuLP can produce highquality partitions of realworld graphs with billion+ vertices in minutes. Additionally, we find that using XtraPuLP partitions for distributedmemory graph analytics leads to a significant endtoend reduction in execution time.
 Sparse MatrixMatrix Multiplication for Modern Architectures

Mehmet Deveci, Erik G. Boman, and Siva Rajamanickam, Sandia National Laboratories
Sparse matrixmatrix multiplication (SPMM) is an important kernel in high performance computing that is heavily used in the graph analytics as well as multigrid linear solvers. Because of its highly sparse structure, it is usually difficult to exploit the parallelism in the modern shared memory architectures. Although there have been various work studying shared memory parallelism of SPMM, some points are usually overlooked, such as the memory usage of the SPMM kernels. Since SPMM is a servicekernel, it is important to respect the memory usage of the calling application in order not to interfere with its execution. In this work, we study memoryefficient scalable shared memory parallel SPMM methods. We study graph compression techniques that reduce the size of the matrices, and allow faster computations. Our preliminary results show that we obtain upto 14x speedup w.r.t NVIDIA’s cuSPARSE, 30% speedups w.r.t SPMM implementation provided in Intel Math Library while using 65% less memory.
3 Advances in Dynamic Graphs: Algorithms, Applications and Challenges
Wednesday, 1 March 2017
Many interesting phenomena can be modeled as dynamic graphs. For example, in biology, complex interactions of microbes evolve over a period of time; in cybersecurity, malicious activities evolve over a period of time through complex interactions with the system; and in transportation networks, dynamic analysis of traffic is essential for modeling evacuation plans and contingency measures. Several graph algorithms such as dynamic community detection, network alignment, graph matching and edge cover formulations play a vital role in the study of realworld dynamic networks.
The goal of this minisymposium is to bring together computational researchers and domain experts exploring dynamic graph models, algorithms, and applications of interest. We propose a twopart minisymposium covering problems from application domains in biology (microbial communities, brain networks), cybersecurity (anomaly detection, control systems), and transportation networks. These talks will be augmented with talks on dynamic graph algorithmic modeling, design and development at scale.
Organizers:
 Ananth Kalyanaraman, Washington State University
 Mahantesh Halappanavar, Pacific Northwest National Laboratory
Talks:
 MS157
 Advances in Algorithms and Applications for Dynamic Graphs

Ananth Kalyanaraman, Washington State University; Mahantesh Halappanavar, Pacific Northwest National Laboratory
Over the last decade, dynamic graph formulations have emerged in multiple application sectors. In social networking, the webs for connectivity and social discourse are maintained as complex networks that continuously evolve at rates that make them intractable to store, let alone analyze. In life sciences, highthroughput technologies for genotyping, phenotyping and imaging are being deployed at massive scales, in order to capture dynamic data at various scales. Similar trends also persist in other domainse.g., cybersecurity, urban networks. While the machinery to collect dynamic data at scale have made significant strides, software capabilities and in particular, algorithmic modeling and network characterizations are mostly in their nascent stages.
In this introductory talk, we will provide an overview of some of the notable algorithmic advances for dynamic networks analysis, as motivated by several application usecases in the life sciences, cybersecurity and brain imaging. Specifically, we will focus on algorithms for community detection, graph matching, and network comparison, and their related challenges. Of emphasis will be to explore the connections (or gaps thereof) between algorithmic modeling and real world application. The talk will be followed by other talks that serve to highlight a subset of the specific application usecases in more depth. The second part of the minisymposium will focus on algorithms and network models for dynamic graph analyses.
 Dynamic Networks of Microbial Biofilms

Radu Marculescu and Chieh Lo, Carnegie Mellon University
Cellbased therapeutics is a key component of precision medicine, i.e., the new paradigm for disease prevention and treatment aimed at providing customized healthcare solutions on a patientbypatient basis. While there has been significant progress towards understanding the cellular behavior and controlling individual cells, our understanding still lacks a computational framework able to capture the populationlevel cell interactions and emerging behaviors that are critical to fighting diseases like antibioticresistant infections or cancer.
In this talk, we bring a new perspective on molecular communication and nanonetworking at populationlevel (as opposed to single celllevel) which is critical to engineer cells behavior, reprogram the cellcell communication, and develop new strategies to control the dynamics of population of cells. In particular, we discuss the significance of the networkbased approach to explore the subtleties of bacteria intercellular network and its implications to biofilm dynamics. Indeed, as computational models become more and more powerful, a networkcentric approach to studying cell populations can improve our understanding their social behaviors and possibly help controlling the infectious diseases they cause. This is a major step towards developing new drugs and targeted medical treatments to fight biofilmrelated infections.
 Dynamic Brain Networks

Kristian Eschenberg, Tom Grabowski, and David Haynor, University of Washington
Current functional neuroimaging (fMRI) studies focus primarily on correlational network analyses, though some still apply classical frequency analysis methods. Few, however, consider global spatiotemporal patterns of cortical activity beyond identifying groups of voxels whose signals fluctuate together. In this talk, I will discuss a recently developed modal decomposition algorithm called Dynamic Mode Decomposition (DMD) and its applicability to study global brain activity patterns of fMRI data acquired by the Human Connectome Project (HCP). DMD was developed by Schmid [J. Fluid Mech., 2010] as an equationfree method to model the behavior of complex dynamical systems to identify spatially coherent modes in a flow field. Importantly, each mode is associated with an eigenvalue defining a unique frequency of oscillation and growth/decay rate. So far, DMD has been applied to the analysis of brain sleep spindles using EEG in a small data set by Brunton et al. [arXiv, 2014], but has not yet been applied in a largescale population study or to highresolution fMRI data such as that acquired by the HCP. I will discuss how we can use DMD’s dynamic modes to build new graphical representations of the cortex, and also how we can use them to shed light on the relationship that various factors like age and neurological disorders (such as Alzheimers and Schizophrenia) have with brain function.
 Quantitative Assessment of Transportation Network Vulnerability with Dynamic Traffic Simulation Methods

Venkateswaran Shekar, University of Massachusetts, Dartmouth; Samrat Chatterjee and Mahantesh Halappanavar, Pacific Northwest National Laboratory; Lance Fiondella, University of Massachusetts, Dartmouth
Safe, secure, and reliable operation of our nation's transportation networks is critical for sustaining modern society. This includes mitigating congestion and assessing impacts of natural, accidental, and intentional disruptions to such networks. Past research on transportation network vulnerability has primarily focused on static traffic models, many of which are formulated as traditional optimization problems. However, transportation networks are dynamic because their usage varies over time. As a result, a realistic characterization of network vulnerability must account for these dynamic properties. This talk describes a dynamic traffic simulationbased approach to assess the vulnerability of transportation networks to disruptions. The approach includes prioritization of critical links over time and is generalizable to the case where both link and node disruptions are of concern. Motivating case study examples are presented and insights into the time varying criticality of links are discussed.
 MS184
 Models for Principled Characterization of Dynamic, Spatially Embedded, Multiscale Networks

Danielle S. Bassett and Richard Betzel, University of Pennsylvania
Advances in neuroimaging techniques have made it possible to reconstruct wholebrain networks composed of structural (physical fiber tracts) and functional (statistical relationships) connections among brain regions. Analysis of these static networks has revealed a host of nonrandom attributes, including highly connected hubs, modular architecture, and rich clubs. In this talk I will discuss two recent advances in brain network modeling. First, I will introduce the multilayer network model for characterizing timevarying functional brain networks. I will cover recent work showing that the brain’s flexibility – the extent to which its multilayer modular organization is stable across time – can be used to predict an individual’s learning rate, is associated with executive function and state of arousal, and is also altered in psychiatric diseases such as schizophrenia. Second, I will discuss the role that the brain’s intrinsic geometry plays in shaping its network architecture. I will cover two recent studies – one in which we show that simple wiring rules can explain a wide variety of the brain’s topological features and another in which we modify classical community detection tools to uncover spaceindependent community structure in brain networks.
 Scalable Algorithms for Graph Matching and Edge Cover Computations

Alex Pothen and Arif Khan, Purdue University; Mostofa Patwary and Pradeep Dubey, Intel Labs
Computing a matching and an edge cover in a graph are two basic problems in computer science, with many applications in network science, machine learning, computational science and engineering, etc. Most variants of matching and edge cover problems can be solved in polynomial time, yet the running times are high and the algorithms are sophisticated. It is even more challenging to design parallel algorithms, since many algorithms rely on searching for long paths in a graph, or implicitly communicate information along long paths, and thus have little concurrency.
We design new approximation algorithms for variant matching and edge cover problems that have high concurrency. For bMatching, we obtain a 1/2approximation algorithm; and for bEdge cover, we describe a 3/2approximation algorithm. Both algorithms have been implemented on shared memory and distributed memory machines, and we report results from tens of thousands of cores. We also discuss some applications of bMatchings and bEdge covers.
 MassiveScale Streaming Analytics for Dynamic Graphs

David A. Bader, Georgia Institute of Technology
Emerging realworld graph problems include: detecting community structure in large social networks; improving the resilience of the electric power grid; and detecting and preventing disease in human populations. Unlike traditional applications in computational science and engineering, solving these problems at scale often raises new challenges because of the sparsity and lack of locality in the data, the need for additional research on scalable algorithms and development of frameworks for solving these problems on high performance computers, and the need for improved models that also capture the noise and bias inherent in the torrential data streams. In this talk, the speaker will discuss the opportunities and challenges in massive dataintensive computing for applications in computational science and engineering.
 Dynamic Network Analysis: From Inference to Insight

Tanya Y. BergerWolf, University of Illinois, Chicago
From gene interactions and brain activity to cellphone calls and zebras grazing together, large, noisy, and highly dynamic networks of interactions are everywhere. Unfortunately, in this domain, our ability to analyze data lags substantially behind our ability to collect it. Moreover, we may be collecting the wrong data for the questions we want to answer in the first place. From collecting the data and inferring the networks to producing meaningful insight at scale, challenges are there every step of the way and computational approaches have been developed to meet those challenges.
We will present computational approaches that address some of the questions about dynamic interaction networks: whom should we sample? how often? what is the “right" network? what are the meaningful patterns and trends? and how can we use the network to gain insight into other aspects of the node behavior? The methods leverage the topological graph structure of the networks and the size of the available data to, somewhat counterintuitively, to produce more accurate results faster. We will demonstrate the scientific implications of the computational analysis on networks of zebras, baboons, and interacting brains cells.
4 HighPerformance Streaming Graph Analysis
Thursday, 2 March 2017
Graph analysis extracts information from relationship data prevalent in network security, health informatics, finance, and many other fields. The modeled relationships change over time, sometimes very rapidly. Repeatedly reanalyzing massive graphs often does not keep up with performance requirements. Applications that monitor and respond to data streams can have low latency requirements. For example, analyzing a 10 gigabit Ethernet in real time requires handling over 130,000 network flows per second or an average latency of under 7.7 microseconds. New algorithms and systems can leverage scattered, local changes in this streaming data for rapid response. Less latencyintensive environments also benefit from more focused analysis and higher performance. This minisymposium surveys a range of practical algorithms, software systems, and new directions for analyzing realworld streaming graph data.
Organizers:
 Jason Riedy, Georgia Institute of Technology
 Henning Meyerhenke, Karlsruhe Institute of Technology, Germany
Talks:
 MS200
 HighPerformance Analysis of Streaming Graphs

Jason Riedy, Georgia Institute of Technology
Graphstructured data in social networks, finance, network security, and others not only are massive but also under continual change. These changes often are scattered across the graph. Stopping the world to run a single, static query is infeasible. Repeating complex global analyses on massive snapshots to capture only what has changed is inefficient. We discuss requirements for singleshot queries on changing graphs as well as recent highperformance algorithms that update rather than recompute results. These algorithms are incorporated into our software framework for streaming graph analysis, STING (SpatioTemporal Interaction Networks and Graphs).
 Dense Subgraphs in Temporal Networks: Algorithms and Analysis

A. Erdem Sariyüce and Ali Pinar, Sandia National Laboratories
The underlying algorithmic challenge with finding dense graphs is that most standard formulations of this problem (like clique, quasiclique, kdensest subgraph) are NPhard. Furthermore, current dense subgraph finding algorithms usually optimize some objective in stationary settings, and only find a few such subgraphs without providing any structural relations among them. However, the goal is rarely to find the "true optimum," but to identify many (if not all) dense substructures. On the other hand, most realworld networks are highly dynamic, but existing practical dense subgraph finding algorithms are only able to handle stationary graphs. We present algorithms to find dense subgraphs in temporal networks and build the hierarchy structure among them. We also use our algorithms to analyze some realworld networks and present new insights.
 TimeEvolving Graph Processing on Commodity Clusters

Anand Iyer and Ion Stoica, University of California, Berkeley
Realworld graphs are seldom static. Applications that generate graphstructured data today do so continuously, giving rise to an underlying graph whose structure evolves over time. Mining these timeevolving graphs can be insightful, both from research and business perspectives. While several works have focused on some individual aspects of timeevolving graph processing such as efficient incremental computations (e.g., Naiad and its GraphLINQ library), consistent snapshot generation (e.g., Kineograph, LLAMA, DeltaGraph) or storage support for highly dynamic graphs (e.g., Weaver), there exists no general purpose distributed timeevolving graph processing engine.
In this paper, we present Tegra, a timeevolving graph processing system built on a data flow framework. Tegra enables three broad classes of operations on evolving graphs: first, it enables storage, retrieval and bulk trans formation of multiple graph snapshots efficiently using a structuresharing persistent data structure based index. Second, it supports temporal graph analysis tasks such as evolutionary queries using a novel timelapse abstrac tion that lets it process multiple snapshots simultaneously with low overhead. Finally, Tegra enables a lightweight dynamic computation model, based on the GatherApply Scatter (GAS) decomposition model, that lets it do sliding window analytics on streaming graphs. Our evaluation of Tegra on realworld datasets show promising results.
 Parallel and Streaming Methods for RealTime Analysis of Dense Structures from Graphs
 Srikanta Tirthapura, Apurba Das, A. Pavan, and Michael Svendsen, Iowa State University; Kanat Tangwongsan, Mahidol University International College, Thailand; KungLun Wu, IBM T.J. Watson Research Center
 MS226
 On Betweenness Centrality Problems in Dynamic Graphs
 Elisabetta Bergamini and Henning Meyerhenke, Karlsruhe Institute of Technology, Germany
 Predicting Movement of Vertices Across Communities in Dynamic Networks

Sriram Srinivasan and Sanjukta Bhowmick, University of Nebraska, Omaha
As dynamic networks evolve, a certain percentage of vertices can migrate to a different community or form a new community(ies). In this presentation, we present an algorithm on how to identify such vertices. We use a metric known as permanence, which measures by how much a vertex belongs to a community. Identifying the migrating vertices can be used to predict the structure of the dynamic communities as well as the effect of the perturbation in the network.
 LargeScale Dynamic Graph Processing on HPC Systems

Keita Iwabuchi, Tokyo Institute of Technology, Japan; Roger Pearce and Maya Gokhale, Lawrence Livermore National Laboratory; Satoshi Matsuoka, Tokyo Institute of Technology, Japan
In many graph applications, the structure of the graph changes dynamically over time and may require real time analysis. However, most prior work for processing large graphs on HPC, e.g., Graph500, has not focused on a dynamic graphs, rather static only. To address this issue, we have developed algorithms, data structures, and infrastructure management necessary to support dynamic graph analysis at large scale on distributed HPC platforms, including next generation supercomputers which have locally attached NVRAM. We have explored support for online dynamic graph processing using an eventcentric infrastructure in HavoqGT. When the graph structure or vertex/edge attributes change, HavoqGT triggers an algorithmic event that allows userdefined callbacks to perform the necessary application updates.
In this talk we discuss our DegAwareRHH datastore designed for storing and indexing dynamic graphs persistently on nodelocal NVRAM storage. We demonstrate its performance scaling out to store large, scalefree graphs by leveraging compact hash tables with high data locality. We extend DegAwareRHH for distributed memory using the eventcentric infrastructure in HavoqGT. Using DegAwareRHH, we demonstrate performance of a dynamic graphcolouring algorithm using a large scale realworld dynamic graph from Wikipedia's edit history.
 Creating Dynamic Graphs from Temporal Data

Anita Zakrzewska, Georgia Institute of Technology
In recent years, there has been a growing interest in the analysis of dynamic graphs, which represent relationships and interactions changing over time. Often, analysis is performed under the assumption that a dynamic graph already exists. However, dynamic graphs usually must be created from an underlying temporal stream of edges and it is necessary to choose a method of doing so. Specifically, new data from the stream must be added and old or less relevant data must be aged off. The approach used affects the structure of the resulting dynamic graph and will therefore affect both data analysis results and performance. This talk analyzes methods of aging off old data to create dynamic graphs.