Abstract

A multilayer network is a powerful and expressive mathematical tool for modeling and analyzing social, economic, biological, and technological systems. Informally, a multilayer network is a collection of related graphs. Applications of multilayer networks include understanding social networks, economic systems, online marketplaces, and detecting vulnerabilities in cyber-physical systems. While this research area is rapidly growing, there is a dearth of computational tools for analyzing large-scale networks from diverse applications. This project will develop the theoretical foundations and software infrastructure for analyzing very large multilayer networks on modern computing systems, thereby enabling their widespread use in diverse applications.
This project will develop NetSplicer, a collection of scalable high-performance algorithms for multilayer-network analysis. The approaches in NetSplicer will be based on a divide-and-conquer-like technique called network decoupling. Using decoupling, the multilayer network can be subdivided into multiple components, each of which could be potentially analyzed using known graph algorithms. Network decoupling seeks to address issues that are critical for multilayer analysis, such as reducing information loss and preserving structural and semantic information. The challenges in efficiently applying network decoupling include determining optimal decoupling strategies, preserving the structure and content of multilayer networks that have multiple vertex and edge types, and developing architecture-aware scalable algorithms that apply across different layers of a network. This project will provide a new capability for multiple research communities and will build a repository for multilayer networks. The planned collaborations with domain scientists from academia and industry, as well as curriculum development and outreach activities, will shape project development efforts to maximize impact.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Collaborating Institution PIs

Year 2 UTA Project Accomplishments (July 1, 2021 to June 30, 2022)

Significant Results

1. Developed two separate heuristic-based algorithms for computing degree centrality and closeness centrality, respectively, for homogeneous MLNs using the decoupling approach. Extensive experimental analysis has been conducted to validate the heuristics with experimental results. For each algorithm, multiple-heuristics which improve upon the previous one for accuracy.

2. Developed separate heuristic-based algorithms for degree and betweenness centrality, respectively, for heterogeneous MLNs with extensive experimental analysis. Again, these multiple heuristic-based approaches improve upon the accuracy as additional information is retained and used during decomposition

3. Our general hypothesis that keeping more information during layer processing can lead to better accuracy has also been established for both homogeneous and heterogeneous MLNs

4. Developed a substructure discovery algorithm for homogeneous MLNs using the decoupling approach. Composition is performed after each iteration and missing substructures are generated. Accuracy of this approach is hundred percent.

5. We have shown how MLN modeling, usage, and analysis for knowledge discovery can be used in a complete life-cycle analysis with a principled approach to converting an EER (Enhanced Entity Relationship) diagram to MLN

6. Significant progress has been made on the MLN dashboard. All component modules: layer generation, MLN analysis, front end GUI have been designed. Working on the design of result visualization

Publications

Types: J - Journal, C- Conference, B/CH - Books/ Chapters Edited, R - Research Report, S - Symposium, W - Workshop Paper, TR - Technical Report, MS - MS Thesis, PhD - PhD Thesis, O - Other

Type	Name and URL
C	Modi, H., Santra, A., and Chakravarthy, S. MR-GQP: Leveraging map/reduce to scale graph query processing. In CIKM ’22: The 31st ACM International Conference on Information and Knowledge Management, Atlanta, Georgia, USA, October 17 - 22, 2022
MS	Mukunda, K. Decoupling-based Approach to Centrality Detection in Heterogeneous Multilayer Networks. Master’s thesis, The University of Texas at Arlington, August 2021. click here
C	Pavel, H. R., Santra, A., and Chakravarthy, S. Closeness centrality algorithms for multilayer networks. In Proceedings of the 14th International Joint Conference on ECML-PKDD 2022, Grenoble, September 2022, Under Review
C	Pavel, H. R., Santra, A., and Chakravarthy, S. Degree centrality algorithms for homogeneous multilayer networks. In Proceedings of the 14th International Joint Con- ference on Knowledge Discovery, Knowledge Engineering and Knowledge Management, IC3K 2022, October 24-26, 2022, Under Review
C	Rademacher, D., Valdez, J., Memeti, E., Samant, K., Santra, A., and Chakravarthy, S. Modviz: A modular and extensible architecture for drill-down and visualization of complex data. In Databases and Information Systems - 15th Interna- tional Baltic Conference, DB&IS 2022, Riga, Latvia, July 4-6, 2022
J	Santra, A., Komar, K. S., Bhowmick, S., and Chakravarthy, S. From base data to knowledge discovery - A life cycle approach - using multilayer networks. Data and Knowledge Engineering (2022), Submitted with Minor Revision.

Participants

First Name	Last Name	Project Role	Contribution	Funding Support	International Collaboration
Abhishek	Santra	Post Doc	Centrality detection algorithms + MLN Dashboard design	Yes	No
Kiran	Bolaj	MS Thesis	Substructure algos for HeMLN	No	no
Arshdeep	Singh	MS Thesis	Substructure algos for HoMLN	no	no
David	Rademacher	REU	MLN analysis module	Yes	No
Jacob	Valdez	REU	MLN dashboard: GUI	Yes	No
Richard	Robertson	REU	MLN Dashboard: Analysis	Yes	No
Kiran	Mukunda	MS Thesis	Degree and betweenness Centrality Algorithms for HeMLN	No	No
Hamza	Pavel	Researcher	Degree and Closeness Centrality Algorithms for HoMLN	No	No
Sachit	Satyal	PhD student	Substructure discovery Algorithms: Map/Reduce optimizations  and decoupling-based algos for HoMLN	No	No
Tulasi	Nakka	PhD student	Stress betweenness Centrlity Algorithms for HeMLN	No	No
Pratik	Dhakal	REU	MLN Dashboard: Analysis	Yes	No

Year 1 UTA Project Accomplishments (July 1, 2020 to June 30, 2021)

Significant Results

1. Developed two algorithms for computing community for homogeneous MLNs using AND composition of layers. Both are better than the naive algorithm. The second algorithm improves accuracy with respect to the first one. First algorithm uses less information from participating layers (only node information from communities). The second one included edge information from communities. In both cases, efficiency of decoupled algorithms is shown to be significantly better than the ground truth algorithm. Ground truth is computed by literally ANDing the two layers (graphs) and computing the community on the result.

2. Developed several approaches for computing the community for homogeneous MLNs using OR composition. Each approach uses a heuristic, which improves upon the previous one.

3.  For both AND and OR community algorithms, we have shown how different types of layers in terms of community and network characteristics have an impact on the overall accuracy. We have come up with similarity thresholds which lead to greater accuracies for the proposed approaches.

4.  For degree and closeness centrality computation for homogeneous MLN layers, we have come up with 4 heuristics where we have shown the trade-off between accuracy and efficiency with respect to the ground truth computation. More specifically, carrying forward more information from the each layer enhances the accuracy, however the efficiency drops slightly due to added overhead

5. A new computation of community for heterogeneous MLNs has been developed using the bipartite match algorithms. This computes communities directly on MLNs using the decoupling approach. Several community characteristics can be use as parameters for computing a MLN community
6. The Cowiz dashboard was extended to Cowiz++ to include time-lime mapping of various fearures of Covid data in addition to showing them on te US map.

Publications

Types: J - Journal, C- Conference, B/CH - Books/ Chapters Edited, R - Research Report, S - Symposium, W - Workshop Paper, TR - Technical Report, MS - MS Thesis, PhD - PhD Thesis, O - Other

Type	Name and URL
C	Samant, K., Memeti, E., Santra, A., Karim, E., and Chakravarthy, S. Cowiz: Interactive covid-19 visualization based on multilayer network analysis. In 37th IEEE International Conference on Data Engineering, ICDE 2021, Chania, Crete, Greece, April 19-22, 2021 (2021). Cowiz Dashboard and Video demo
C	Komar, K. S., Santra, A., Bhowmick, S., and Chakravarthy, S. EER → MLN: EER approach for modeling, mapping, and analyzing complex data using multilayer net- works (mlns). In Conceptual Modeling - 39th International Conference, ER 2020, Vi- enna, Austria, November 3-6, 2020, Proceedings (2020), G. Dobbie, U. Frank, G. Kappel, S. W. Liddle, and H. C. Mayr, Eds., vol. 12400 of Lecture Notes in Computer Science, Springer, pp. 555–572.
PhD	Santra, A. Analysis of Complex Data Sets Using Multilayer Networks: A Decoupling- based Framework. PhD thesis, The University of Texas at Arlington, July 2020. click here
MS	Rai, A. MLN-SUBDUE: Decoupling Approach-based Substructure Discovery In Mul- tilayer Networks (MLNs). Master’s thesis, The University of Texas at Arlington, May 2020. click here
MS	Modi, H. MR-QP: A Scalable Approach To Query Processing On Arbitrary-size Graphs Using The Map/Reduce Framework. Master’s thesis, The University of Texas at Ar- lington, May 2020. click here
TR	Santra, A., Komar, K. S., Bhowmick, S., and Chakravarthy, S. A new community definition for multilayer networks and A novel approach for its efficient computation. CoRR abs/2004.09625 (2020). click here
J	Das, S., Santra, A., Bodra, J., and Chakravarthy, S. Query processing on large graphs: Approaches to scalability and response time trade offs. Data Knowl. Eng. 126 (2020), 1017–1036.
C	Vu, X.-S., Santra, A., Chakravarthy, S., and Jiang, L. Generic multilayer network data analysis with the fusion of content and structure. In Computational Linguistics and Intelligent Text Processing - 20th International Conference, CICLing 2019, La Rochelle, France, April 7-13, 2019 (2019)
TR	Santra, A., Komar, K. S., Bhowmick, S., and Chakravarthy, S. Making a case for mlns for data-driven analysis: Modeling, efficiency, and versatility. CoRR abs/1909.09908 (2019). click here
MS	Komar, K. Data-Driven Modeling of Heterogeneous Multilayer Networks And Their Community-Based Analysis Using Bipartite Graphs. Master’s thesis, The University of Texas at Arlington, August 2019. click here
B/Ch	Chakravarthy, S., Santra, A., and Komar, K. S. Why multilayer networks instead of simple graphs? modeling effectiveness and analysis flexibility and efficiency! In Big Data Analytics - 7th International Conference, BDA 2019, Ahmedabad, India, December 17-20, 2019, Proceedings (2019), S. Madria, P. Fournier-Viger, S. Chaudhary, and P. K. Reddy, Eds., vol. 11932 of Lecture Notes in Computer Science, Springer, pp. 227–244.
J	Das, S., and Chakravarthy, S. Duplicate reduction in graph mining: Approaches, analysis, and evaluation. IEEE Trans. Knowl. Data Eng. 30, 8 (2018), 1454–1466.
B/Ch	Chakravarthy, S., Santra, A., and Komar, K. S. Humble data management to big data analytics/science: A retrospective stroll. In Big Data Analytics - 6th International Conference, BDA 2018, Warangal, India, December 18-21, 2018, Proceedings (2018), A. Mondal, H. Gupta, J. Srivastava, P. K. Reddy, and D. V. L. N. Somayajulu, Eds., vol. 11297 of Lecture Notes in Computer Science, Springer, pp. 33–54.
C	Santra, A., Bhowmick, S., and Chakravarthy, S. Efficient community re-creation in multilayer networks using boolean operations. In International Conference on Compu- tational Science, ICCS 2017, 12-14 June 2017, Zurich, Switzerland (2017), P. Koumout- sakos, M. Lees, V. V. Krzhizhanovskaya, J. J. Dongarra, and P. M. A. Sloot, Eds., vol. 108 of Procedia Computer Science, Elsevier, pp. 58–67.
C	Santra, A., Bhowmick, S., and Chakravarthy, S. Hubify: Efficient estimation of central entities across multiplex layer compositions. In 2017 IEEE International Conference on Data Mining Workshops, ICDM Workshops 2017, New Orleans, LA, USA, November 18-21, 2017 (2017), R. Gottumukkala, X. Ning, G. Dong, V. Raghavan, S. Aluru, G. Karypis, L. Miele, and X. Wu, Eds., IEEE Computer Society, pp. 142–149.
C	Santra, A., and Bhowmick, S. Holistic analysis of multi-source, multi-feature data: Modeling and computation challenges. In Big Data Analytics - 5th International Con- ference, BDA 2017, Hyderabad, India, December 12-15, 2017, Proceedings (2017), P. K. Reddy, A. Sureka, S. Chakravarthy, and S. Bhalla, Eds., vol. 10721 of Lecture Notes in Computer Science, Springer, pp. 59–68.

Participants

First Name	Last Name	Project Role	Contribution	Funding Support	International Collaboration
Abhishek	Santra	Post Doc	Centrality detection algorithms + MLN Dashboard design	Yes	No
David	Rademacher	REU	MLN analysis module	Yes	No
Endrit	Memeti	REU	Cowiz + Dashboard	Yes	No
Kunal	Samant	REU	Cowiz + Dashboard	No	No
Jacob	Valdez	REU	MLN dashboard GUI	Yes	No
Anish	Rai	MS Thesis	Substructure discovery on HoMLN	No	No
Harshit	Modi	MS Thesis	Querying large graphs using M/R	No	No