Supercomputing and Computation

SHARE

Discrete Math


Many complex systems of importance to DOE consist of networks of discrete components - for example, cyber networks, the electric power grid, social networks - whose behavior can drive energy demand, and biological (e.g. gene regulatory or metabolic) networks. Furthermore, the networks of interest to DOE are often very large, containing hundreds of millions of elements or more, and can range from relatively static in structure (e.g. the power grid), to rapidly changing and evolving (e.g. social networks). Mathematical analysis and models of complex networks can be used to computationally explore many practical questions about the performance and behaviors of real systems. Much of the existing research on complex networks has focused primarily on the identification of important invariant properties including degree distribution, clustering coefficients, shortest-paths, and connectivity. However, these properties tend to measure either very "local" interactions or very "global" properties, and thus often fail to capture the dynamics of processes on the network, where the characteristics of the coupling between local structure and network-wide phenomena is critical. The discrete mathematics research at ORNL currently focuses on elucidating and utilizing this "intermediate scale" structure in complex networks to enable scalable analysis and expand the types of queries which can be run on massive graphs/datasets. This includes work on developing new algorithms and implementations for solving graph optimization problems using tree decompositions and dynamic programming on parallel HPC architectures; integrating structural graph theory constructs with ideas from hyperbolic geometry and metric spaces to better define an intermediate scale "skeleton" for networks; and developing approaches to problems in dimensionality reduction which take advantage of network structure to avoid densification of sparse graph data. ORNL is also represented on the steering committee for the Graph 500 benchmark, which aims to provide performance metrics for data-intensive supercomputing applications to guide hardware and software design for supporting these increasingly important discrete problems.

ASK ORNL

We're always happy to get feedback from our users. Please use the Comments form to send us your comments, questions, and observations.