About the project

Smart Grid Project

* Acknowledgement:

“This material is based upon work supported by the National Science Foundation under Grant Nos.1533918 and 1533881.”

* Disclaimer:

"Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.” 

* Award numbers (collaborative awards):

https://www.nsf.gov/awardsearch/showAward?AWD_ID=1533918

https://www.nsf.gov/awardsearch/showAward?AWD_ID=1533881 

Duration (expected): Sept 2015 - August 2019

Award Title: XPS: EXPL: FP: Collaborative Research: SPANDAN: Scalable Parallel Algorithms for Network Dynamics Analysis

PIs: Sajal K. Das and Sanjukta Bhowmick

Student(s): Sriram Srinivasan, Sima Das, Shubham Pandey

 

  • Project Goals:

The goal of our SPANDAN project is to create a novel architecture-independent framework for designing efficient, portable and scalable parallel algorithms for analyzing large-scale dynamic networks (e.g., updating important properties). SPANDAN will not only provide an intuitive methodology for efficiently translating sequential algorithms into scalable parallel algorithms for dynamic networks, but also provide mechanisms for their analytical evaluation and serve as a mediatory layer between applications and system level tuning. 

As the underlying methodology, the SPANDAN framework will exploit graph sparsification techniques to divide the network into sparse subgraphs (certificates) that form the leaves of a sparsification tree. This innovative approach will lead to the design and analysis of efficient parallel algorithms for updating dynamic networks, and reduction of memory latency associated with parallelizing unstructured data. Specifically parallel algorithms will be designed for maintaining network topological characteristics, and updating influential vertices and communities. To demonstrate portability and performance, the developed algorithms will be implemented on the distributed memory clusters, shared memory multicores, and massively multithreaded machines.

  • Research Challenges:

The main challenge in developing scalable algorithms is the poor locality of access associated with graph traversals. Poor locality leads to increased computational resources including computation time and power requirements, and also reduces opportunities for scalability

  • Current/Final Results (summary):
  • Designing the first parallel algorithm for updating MST, including both addition and deletion of edges;
  • Developing a template for updating similar tree-based structures;
  • Classifying networks based on their stability to noise, and developing an algorithm from predicting high centrality vertices in time varying networks;
  • Extending the concept of assortative rich clubs of degrees to path based centralities;
  • Demonstrating that networks are stable if their inner cores are expander-like graphs.
  • Proving that multiple time scales (e.g., microscopic and macroscopic time frames) along with local (link level) and semi-global (cluster level) structural evolution with correlation can be leveraged to accurately compute future links in dynamically evolving networks.

* Publications

Below is the list of papers published in 2017-2018. Older papers are available at https://graphsparsification.herokuapp.com/index.html

  1. S. Sarkar, S. Sikdar, A. Mukherjee and S. Bhowmick “Using Core-Periphery Structure to Predict High Centrality Nodes in Time Varying Networks,” Data Mining and Knowledge Discovery, to appear, 2018.
  2. A. Mukherjee and S. Bhowmick, “On Rich Clubs of Path-Based Centrality Networks,” accepted inConference on Information and Knowledge Management (CIKM), 2018.
  3. S. Srinivasan, S. Pollard, B. Norris, S. K. Das and S. Bhowmick, “A Shared Memory Algorithm for Updating Tree based Properties of Large Dynamic Networks,” IEEE Transactions on Big Data, (Special Issue on the Integration of Extreme Scale Computing and Big Data Management and Analytics), accepted to appear, 2018.
  4. A. Sturaro, S. Silvestri, M. Conti, and S. K. Das, “A Realistic Model for Failure Propagation in Interdependent Cyber-Physical Systems,” IEEE Transactions on Network Science and Engineering (Special Issue on Network Science for High-Confidence Cyber-Physical Systems), to appear, 2018.
  5. C. Vallati, S. Brienza, G. Anastasi, and S. K. Das, “Improving Network Formation in 6TiSCH Networks,”IEEE Transactions on Mobile Computing, to appear, 2018.
  6. Y. Wan, J. Yan, Z. Lin, V. Sheth, and S. K. Das, “On the Structural Perspective of Computational Effectiveness for Quantized Consensus in Layered UAV Networks,” IEEE Transactions on Control of Network Systems, to appear, 2018.
  7. B. Jedari, F. Xia, H. Chen, S. K. Das, A. Tolba, and Z. Al-Makhadmeh, “A Social-based Watchdog System to Detect Selfish Nodes in Opportunistic Mobile Networks,” Future Generation Computer Systems, to appear, 2018.
  8. A. Rahim, X. Kong, F. Xia, Z. Ning, N. Ullah, J. Wang, and S. K. Das, “Vehicular Social Networks: A Survey,” Pervasive and Mobile Computing, 43: 96-113, 2018.
  9. S. Das and S. K. Das, “A Stochastic Model for Computing Future Links in Large Scale Social Networks,”IEEE Transactions on Computational Social Systems (Special Issue on Parallel and Distributed Processing for Computational Social Systems), in revision, 2018.

 

* Software Downloads 

Codes for the shared memory MST update can be found at (https://graphsparsification.herokuapp.com/index.html).

 

* Broader Impacts

 To evaluate the effectiveness of SPANDAN framework in real-world applications, the PIs are collaborating with social scientists and biologists. They also integrated research findings into various courses such as applied graph theory, distributed computing, network analysis, and parallel algorithms. As part of outreach, they have proactively encouraged women and minority students to pursue IT-related careers. A female student at Missouri S&T have graduated with PhD degree, and a female M.S. student at University of Nebraska - Omaha has been mentored. A workshop on the effect of noise in biological networks was organized in conjunction with IEEE International Conference on Bioinformatics and Biomedicine (BIBM) in 2017.

 

* Point of Contact: Sajal K. Das (sdas@mst.edu)

* Date of last Update: August 30, 2018