Article
Mathematics
Sasmita Barik, Debabrota Mondal, Sukanta Pati
Summary: The study in 2006 showed that only corona trees among the non-singular trees satisfy a specific eigenvalue property, leaving a general question open about trees with reciprocal eigenvalues. However, it was found that there are no such trees with at least two vertices. The proof involves a beautiful application of graph products.
LINEAR & MULTILINEAR ALGEBRA
(2022)
Article
Mathematics, Applied
Modjtaba Ghorbani, Xueliang Li, Samaneh Zangi, Najaf Amraei
Summary: This paper investigates the extended adjacency matrix of a graph, explores its spectral properties and provides lower and upper bounds on the extended adjacency spectral radii. Additionally, the behavior of the extended adjacency energy of the graph is studied.
APPLIED MATHEMATICS AND COMPUTATION
(2021)
Article
Mathematics, Applied
Bo-Jun Yuan, Yi Wang, Yi-Zheng Fan
Summary: The paper proves the existence of a partial orientation sigma with respect to T for a connected graph G, such that the largest eigenvalue of the resulting graph's Hermitian adjacency matrix satisfies a specific condition.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2021)
Article
Automation & Control Systems
Keith D. Levin, Fred Roosta, Minh Tang, Michael W. Mahoney, Carey E. Priebe
Summary: This paper investigates the out-of-sample extension problem for graph embedding techniques, proving that out-of-sample extension based on a random dot product graph follows a central limit theorem. It provides a convenient framework for analyzing trade-offs between estimation accuracy and computational expenses, and demonstrates the performance of out-of-sample extensions on simulated and real-world data, showing significant computational savings with minimal loss in embedding quality.
JOURNAL OF MACHINE LEARNING RESEARCH
(2021)
Article
Mathematics, Applied
Ali Raza, Mobeen Munir, Tasawar Abbas, Sayed M. Eldin, Ilyas Khan
Summary: The article focuses on the spectrum-based characteristics of generalized prism graphs and their applications in computing network-related quantities.
Article
Polymer Science
Ziyu Xing, Dong-Wei Shu, Haibao Lu, Yong-Qing Fu
Summary: In this study, a graph theory was employed to describe the coupling relationship between vertices and edges in molecular networks, and a undirected graphical model was formulated to model the dynamic elasticity of polyelectrolyte hydrogel. The coupling relationship between vertices and edges was obtained using end-to-end distance and viscosity parameters. The effectiveness of the undirected graphical model was verified using both finite element analysis and experimental results.
Article
Physics, Multidisciplinary
Junjie Lu, Tobias Hofmann, Ulrich Kuhl, Hans-Juergen Stoeckmann
Summary: Quantum graphs are useful for studying the spectral statistics of chaotic systems. Neumann and Dirichlet graphs have different boundary conditions at the vertices. The Neumann spectral statistics deviate from random matrix predictions due to the interlacing theorem. We provide analytic expressions for level spacing distribution and number variance of ensemble averaged spectra of Dirichlet graphs, and compare them with numerical results. The deviations of numerical results for small Neumann graphs from random matrix predictions are also discussed.
Article
Chemistry, Multidisciplinary
Sunoh Choi
Summary: With the rapid growth of the internet, there has been an increase in malicious files, particularly in the use of PowerShell scripts and Windows PE files for malicious behaviors. Artificial intelligence-based malware detection methods, such as GCN, have been widely studied to address these issues. By proposing a method for malicious PowerShell detection using GCN and generating an adjacency matrix using Jaccard similarity, the detection rate for malicious PowerShell has been increased by approximately 8.2%.
APPLIED SCIENCES-BASEL
(2021)
Article
Mathematics, Applied
Zhenan Shao, Xiying Yuan
Summary: This paper proves that there exists a switching operation in certain classes of graphs, such that all eigenvalues of the resulting signed graph are main eigenvalues.
APPLIED MATHEMATICS AND COMPUTATION
(2022)
Article
Chemistry, Analytical
Muhammad Umair, Young-Koo Lee
Summary: This paper investigates graph compression techniques and proposes a method that improves the compression ratio by decomposing a graph into sub-matrices and using variable-shaped regions. The proposed approach achieved a 93.8% compression ratio on average in empirical evaluation.
Article
Computer Science, Information Systems
Yuchen Zhang, Wenrui Dai, Yong Li, Chenglin Li, Junhui Hou, Junni Zou, Hongkai Xiong
Summary: This paper proposes a novel framework for light field image compression that utilizes graph learning and dictionary learning techniques to remove structural redundancies between different views. The framework achieves significant reduction in bit-rates by sampling and encoding only a few key views and reconstructing non-key views using the graph adjacency matrix learned from angular patches. Dictionary-guided sparse coding is used to compress the graph adjacency matrices and reduce coding overheads.
IEEE TRANSACTIONS ON MULTIMEDIA
(2023)
Article
Mathematics
G. Pasten, O. Rojo
Summary: This paper investigates the adjacency matrix A(G) and distance matrix D(G) defined by the connected graph G, and extends it to the adjacency-distance matrix S(G), which is further generalized as the convex linear combination S(a)(G). The focus of this study is on the spectral radius ?(S-a(G)) of S-a(G), and some results of S(G) are extended to certain subintervals of [0, 1]. For a ? [1/2, 1], the trees with the maximum and minimum ?(S-a(G)) among trees of fixed order are determined, and it is proved that ?(S-a(G)) is a branching index. Moreover, for a ? (1/2, 1], the graphs that uniquely minimize ?(S-a(G)) among all connected graphs of fixed order and fixed connectivity, as well as among all connected graphs of fixed order and fixed chromatic number, are characterized.
LINEAR & MULTILINEAR ALGEBRA
(2023)
Article
Automation & Control Systems
Manoj Kumar, Anurag Sharma, Sandeep Kumar
Summary: Graph coarsening is a dimensionality reduction technique for large-scale graph machine-learning problems. Existing methods only focus on the graph matrix, while this paper proposes a novel framework that considers both the graph matrix and the node features to learn and simplify the graph structure using optimization methods.
JOURNAL OF MACHINE LEARNING RESEARCH
(2023)
Article
Mathematics, Applied
Hongyu Wang, Xinmin Hou, Yue Ma
Summary: In this article, the author determines the exact value of spex(n, {Kk+1, Ms+1}) for large n, which provides the spectral version of the result by Alon and Frankl.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2023)
Article
Chemistry, Multidisciplinary
Manuja Kothiyal, Santosh Kumar, N. Sukumar
Summary: This study investigates the network characteristics of different chemical libraries using conventional graph measures and random matrix theory. It finds that the degree assortativity and long-range fluctuation statistics in eigenvalue space respond to changes in the network structure and chemical space. The findings provide guidance for designing high-throughput screening libraries for different drug design applications.
JOURNAL OF MATHEMATICAL CHEMISTRY
(2022)
Article
Multidisciplinary Sciences
Mark He, Joseph Glasser, Nathaniel Pritchard, Shankar Bhamidi, Nikhil Kaza
Article
Computer Science, Software Engineering
Louigi Addario-Berry, Shankar Bhamidi, Sanchayan Sen
Summary: This study investigates the fixation time of the leader's identity in the general setting of Aldous's multiplicative coalescent, showing tightness in the Brownian regime and one-sided tightness in the heavy-tailed case. The findings demonstrate differences in the possible behavior in the two regimes, with explicit determination of median value of fixation time and generalization of results on Erdos-Renyi random graph.
RANDOM STRUCTURES & ALGORITHMS
(2021)
Article
Statistics & Probability
Shankar Bhamidi, Danny Nam, Oanh Nguyen, Allan Sly
Summary: This paper establishes the necessary and sufficient criterion for the contact process on Galton-Watson trees or random graphs to exhibit extinction or short survival phases. It is shown that the survival threshold for a Galton-Watson tree is strictly positive if and only if its offspring distribution has an exponential tail. On random graphs with degree distributions, it is demonstrated that the behavior of the contact process varies depending on whether the distribution has an exponential tail or is subexponential.
ANNALS OF PROBABILITY
(2021)
Article
Statistics & Probability
Nelson Antunes, Shankar Bhamidi, Tianjian Guo, Vladas Pipiras, Bang Wang
Summary: This work focuses on estimating the in-degree distribution of directed networks from sampling network nodes or edges. Two estimation approaches are proposed, based on inversion and asymptotic methods. The performance of these approaches is tested on synthetic and real networks, showing good results.
JOURNAL OF COMPUTATIONAL AND GRAPHICAL STATISTICS
(2021)
Article
Statistics & Probability
Sayan Banerjee, Shankar Bhamidi
Summary: The study focuses on evolving network models modulated by two parameters and the emergence of persistent hubs. General conditions for the emergence or lack thereof of persistent hubs were obtained, with specific asymptotic analysis for the case of trees in the absence of persistence. The analysis relies on an inverse rate weighted martingale and provides technical foundations for the main results, including concentration inequalities and moderate deviations.
PROBABILITY THEORY AND RELATED FIELDS
(2021)
Article
Computer Science, Software Engineering
Shankar Bhamidi, Ruituo Fan, Nicolas Fraiman, Andrew Nobel
Summary: The article focuses on random recursive trees grown by community modulated schemes involving random attachment or degree based attachment. General techniques based on continuous time embedding are derived to study these models. Through stochastic analytic techniques, it is shown that key macroscopic statistics of the continuous time embeddings stabilize, allowing asymptotics for various characteristics of the original models to be obtained.
RANDOM STRUCTURES & ALGORITHMS
(2022)
Article
Statistics & Probability
Shankar Bhamidi, Amarjit Budhiraja, Paul Dupuis, Ruoyu Wu
Summary: This paper studies the problem of large deviations in sparse random graph models by establishing large deviation principles on suitable path spaces. The exploration processes and stochastic differential equations are used to analyze the asymptotics of probabilities of non-typical behavior. The paper focuses on the configuration model and provides explicit formulas for decay rates of probabilities of non-typical component degree distributions.
ANNALS OF APPLIED PROBABILITY
(2022)
Article
Statistics & Probability
Shankar Bhamidi, Amarjit Budhiraja, Miheer Dewaskar
Summary: This paper investigates the fluctuations of the state process in the supermarket model. By establishing functional limit theorems, it is shown that the fluctuations of the state process are of order n(-1/2) and are governed asymptotically by a one-dimensional Brownian motion under different growth rate conditions. The limit processes in the three canonical regimes have different forms.
ANNALS OF APPLIED PROBABILITY
(2022)
Article
Statistics & Probability
Sayan Banerjee, Shankar Bhamidi
Summary: We consider models of growing random trees driven by an attachment function, and aim to understand the performance of root finding algorithms. By using the Jordan centrality measure and its variants, we develop techniques for root finding algorithms and derive necessary and sufficient bounds on the budget K(epsilon). We also study the embedding of the models and obtain rates of convergence results to these limits.
ANNALS OF APPLIED PROBABILITY
(2022)
Article
Statistics & Probability
Shankar Bhamidi
Summary: David John Aldous, a mathematician born in the UK in 1952, is known for his seminal contributions to various topics in probability theory. He spent his academic career at the University of California, Berkeley and has received numerous honors and awards for his work.
STATISTICAL SCIENCE
(2022)
Article
Statistics & Probability
Hui Shen, Shankar Bhamidi, Yufeng Liu
Summary: Clustering is a fundamental tool for exploratory data analysis, and statistical significance of clustering (SigClust) is a cluster evaluation method for high-dimensional, low-sample size data. The original SigClust may not work well in certain cases and is not applicable when researchers only have the dissimilarity matrix. To address these issues, we propose a new SigClust method using multidimensional scaling (MDS) to achieve low-dimensional representations of the data and assess the statistical significance of clustering.
JOURNAL OF COMPUTATIONAL AND GRAPHICAL STATISTICS
(2023)
Article
Statistics & Probability
Sayan Banerjee, Shankar Bhamidi, Iain Carmichael
Summary: This study considers dynamic random trees constructed using an attachment function f: N → R+, where a new vertex attaches to an existing vertex in the current tree with probability proportional to the degree of the existing vertex. The effect of a change point in the system is explored, where the attachment function switches from f to another function g at a certain tree size. The study provides deterministic approximations for the evolution of the empirical degree distribution and develops mathematical techniques to analyze both homogeneous and inhomogeneous continuous time branching processes.
ANNALS OF APPLIED PROBABILITY
(2023)
Article
Computer Science, Theory & Methods
Robin Richter, Shankar Bhamidi, Sach Mukherjee
Summary: Causal structure learning (CSL) is the process of estimating causal graphs from data. This paper proposes a new baseline method called graph-based predictors (GBPs), which leverage the known graph structure to provide improved baselines for comparing CSL methods. Experimental results show that GBPs outperform random baselines in practice.
STATISTICS AND COMPUTING
(2023)
Article
Computer Science, Theory & Methods
Nelson Antunes, Sayan Banerjee, Shankar Bhamidi, Vladas Pipiras
Summary: This paper investigates the statistical learning of nodal attribute functionals in homophily networks using random walks. It proposes a generalization of canonical models, based on preferential attachment, and introduces a model class U for theoretical analysis and asymptotics of various functionals. The paper also explores attribute agnostic sampling schemes for statistical learning and proposes estimators for learning attribute distribution, degree distribution, and homophily measures.
APPLIED NETWORK SCIENCE
(2023)
Article
Statistics & Probability
Shankar Bhamidi, Souvik Dhara, Remco van der Hofstad, Sanchayan Sen
Summary: In this paper, we establish the global lower mass-bound property of the largest connected components in the critical window for the configuration model with an infinite third moment in the degree distribution. We extend the scaling limit results of the critical percolation clusters, viewed as measured metric spaces, to the stronger Gromov-Hausdorff-Prokhorov topology under slightly stronger assumptions on the degree distribution. Our result implies the distributional convergence of global functionals such as the diameter of the largest critical components and provides a sufficient condition for the compactness of the random metric spaces in the heavy-tailed regime.
ELECTRONIC JOURNAL OF PROBABILITY
(2022)