With the growing ubiquity of data in network form, clustering in the context of a network, represented as a graph, has become increasingly important. Clustering is a very useful data exploratory machine learning tool that allows us to make better sense of heterogeneous data by grouping data with similar attributes based on some criteria. This paper investigates the application of a novel graph theoretic clustering method, Node-Based Resilience clustering (NBR-Clust), to address the heterogeneity of Autism Spectrum Disorder (ASD) and identify meaningful subgroups. The hypothesis is that analysis of these subgroups would reveal relevant biomarkers that would provide a better understanding of ASD phenotypic heterogeneity useful for further ASD studies. We address appropriate graph constructions suited for representing the ASD phenotype data. The sample population is drawn from a very large rigorous dataset: Simons Simplex Collection (SSC). Analysis of the results performed using graph quality measures, internal cluster validation measures, and clinical analysis outcome demonstrate the potential usefulness of resilience measure clustering for biomedical datasets. We also conduct feature extraction analysis to characterize relevant biomarkers that delineate the resulting subgroups. The optimal results obtained favored predominantly a 5-cluster configuration.

The purpose of this work is four-fold: (1) We propose a new measure of network resilience in the face of targeted node attacks, vertex attack tolerance, represented mathematically as , and prove that for d-regular graphs τ(G) = Θ(Φ(G)) where Φ(G) denotes conductance, yielding spectral bounds as corollaries. (2) We systematically compare τ(G) to known resilience notions, including integrity, tenacity, and toughness, and evidence the dominant applicability of τ for arbitrary degree graphs. (3) We explore the computability of τ, first by establishing the hardness of approximating unsmoothened vertex attack tolerance under various plausible computational complexity assumptions, and then by presenting empirical results on the performance of a betweenness centrality based heuristic algorithm applied not only to τ but several other hard resilience measures as well. (4) Applying our algorithm, we find that the random scale-free network model is more resilient than the Barabasi−Albert preferential attachment model, with respect to all resilience measures considered.

This paper examines a schema for graph-theoretic clustering using node-based resilience measures. Node-based resilience measures optimize an objective based on a critical set of nodes whose removal causes some severity of disconnection in the network. Beyond presenting a general framework for the usage of node based resilience measures for variations of clustering problems, we experimentally validate the usefulness of such methods in accomplishing the following: (i) clustering a graph in one step without knowing the number of clusters a priori; (ii) removing noise from noisy data; and (iii) detecting overlapping communities. We demonstrate that this clustering schema can be applied successfully using a wide range of data, including both real and synthetic networks, both natively in graph form and also expressed as point sets.

We present the first formal network analysis of curricular networks for public institutions, focusing around five midwestern universities. As a first such study of public institutions, our analyses are primarily macroscopic in nature, observing patterns in the overall course prerequisite networks (CPNs) and Curriculum Graphs (CGs). An overarching objective is to better understand CPN variability and patterns across different institutions and how these patterns relate to curricular outcomes. In addition to computing well known network centrality measures to capture courses of importance in the CPNs studied, we have also formulated some newer methods with specific relevance to the curricular domains and corresponding graph types at hand. We have discovered that a new graph theoretic measure of node importance which we call reach, based on the well-known concept of reachability, is needed to more accurately express the critical nature of some introductory courses in a university. Another analytical novelty that we introduce and apply to the subject of CPNs is the Longest Paths Induced sub-Graph (LPIG) of the CPN, which yields information on relatively constrained programs and pathways. Finally, we have established a new connection between clustering of the CG and meta-majors at Southern Illinois University Edwardsville (SIUE), providing clusterings of the other public institution CGs as useful heuristics of major groupings as well. This work is borne from collaboration between academic units and academic advising with hopes of practical benefits towards aiding student advising.

Improving curriculum structure is critical for enhancing student success and on-time graduation, yet few methods exist to evaluate how prerequisite paths shape student progression and graduation outcomes. This study proposes a data-driven, graph-based framework that integrates course prerequisite networks with student performance data to systematically analyze curricular structure and student outcomes. We identify high-risk courses by jointly modeling their structural importance and pass rates, and quantify the time and survivability of different prerequisite paths using probabilistic models. Additionally, we introduced grade transition patterns to capture more nuanced transitions in student performance and pinpoint bottlenecks along prerequisite paths. Applying the model on four science and engineering majors from a public institution, the results not only identify high-risk courses often missed in conventional analyses, but also reveal path-level disparities and structural bottlenecks that affect student progression and time to graduation. For example, in the Computer Science major, we identified that the architecture and operating systems pathway is more challenging than the software engineering pathway. A closer examination of the course pairs along this trajectory revealed that the difficulty stems from a significant drop in student performance between a prerequisite–successor course pairs.This type of analysis fills a gap in conventional curriculum studies, which often overlook path-level dynamics, and offers actionable insights for educators a to identify high risk curricular components.

We are concerned with an appropriate mathematical measure of resilience in the face of targeted node attacks for arbitrary degree networks, and subsequently comparing the resilience of different scale-free network models with the proposed measure. We strongly motivate our resilience measure termed \emph{vertex attack tolerance} (VAT), which is denoted mathematically as $\tau(G) = \min_{S \subset V} \frac{|S|}{|V-S-C_{max}(V-S)|+1}$, where $C_{max}(V-S)$ is the largest connected component in $V-S$. We attempt a thorough comparison of VAT with several existing resilience notions: conductance, vertex expansion, integrity, toughness, tenacity and scattering number. Our comparisons indicate that for artbitrary degree distributions VAT is the only measure that fully captures both the major \emph{bottlenecks} of a network and the resulting \emph{component size distribution} upon targeted node attacks (both captured in a manner proportional to the size of the attack set). For the case of $d$-regular graphs, we prove that $\tau(G) \le d\Phi(G)$, where $\Phi(G)$ is the conductance of the graph $G$. Conductance and expansion are well-studied measures of robustness and bottlenecks in the case of regular graphs but fail to capture resilience in the case of highly heterogeneous degree graphs. Regarding comparison of different scale-free graph models, our experimental results indicate that PLOD graphs with degree distributions identical to BA graphs of the same size exhibit consistently better vertex attack tolerance than the BA type graphs, although both graph types appear asymptotically resilient for BA generative parameter $m = 2$. BA graphs with $m = 1$ also appear to lack resilience, not only exhibiting very low VAT values, but also great transparency in the identification of the vulnerable node sets, namely the hubs, consistent with well known previous work.