Abstract
This paper introduces STruD (Simplicial Truss Decomposition), a novel framework that generalizes truss decomposition from graphs to simplicial complexes. By accounting for $n$-ary relationships, STruD identifies cohesive higher-order communities in complex networks. The authors present a memory-aware, scalable algorithm that utilizes a-priori pruning and out-of-core operations to manage combinatorial complexity. Evaluation on real-world datasets demonstrates that simplicial trussness uncovers structural nuances lost in traditional graph-based analysis and provides a robust filtration for topological data analysis.
Introduction
Traditional network analysis often reduces complex interactions to binary edges. However, many real-world phenomena involve group-based interactions, such as co-authorship or multi-recipient emails. Simplicial complexes offer a more faithful representation of these interactions by modeling them as simplices (triangles, tetrahedra, etc.). While graph truss decomposition is a popular method for finding dense, triangle-rich communities, extending this concept to higher-order structures is computationally challenging due to the "downward closure" property: any interaction among a group implies interactions among all its subgroups.
Methods
STruD defines the Simplicial $k$-truss by introducing "joists"—higher-order structures that provide support for a simplex. To handle the potential combinatorial explosion of data, the algorithm employs several key technical strategies:
- A-priori Pruning: Borrowing from frequent itemset mining, the algorithm uses the property that a $(q+1)$-dimensional simplex cannot have higher trussness than the $q$-dimensional faces it contains. This allows for massive search-space pruning.
- Memory-Aware Architecture: STruD uses a compact inverted index and a strategy that switches to "out-of-core" (disk-based) operations when the dataset exceeds available RAM, ensuring scalability for massive datasets like DBLP.
- Top-N Variant: A specialized version of the algorithm that finds only the most cohesive structures without computing the full decomposition, facilitating rapid exploratory analysis.
Results and Key Insights
The authors evaluated STruD on diverse datasets, including DBLP co-authorship, Enron emails, and financial ETF correlations.
Richness vs. Simplicity
A primary finding is that simplicial trussness reveals structural information that is lost when "flattening" data into a simple graph. For instance, in the ETF dataset, the size distribution of simplicial trusses is concave, whereas the graph-based version is convex. This indicates the presence of significant higher-order clusters that graph-based methods fail to distinguish.
Topological Data Analysis (TDA)
STruD also serves as an effective "filtration" for Persistent Homology. This allows researchers to identify topological features, such as "holes" or "voids," that persist across different levels of cohesion. Furthermore, the authors demonstrate that simplicial trussness can quantify "manifoldness"—how much a dataset deviates from a smooth, locally Euclidean space. Real-world data like DBLP shows highly heterogeneous, "clumpy" behavior compared to perfect manifolds.
Conclusion
STruD provides a scalable and memory-efficient solution for uncovering higher-order cohesion in complex networks. By successfully processing datasets with millions of vertices and identifying structures up to dimension 17, the algorithm proves practical for large-scale analysis. Future work includes parallelizing the algorithm and exploring its application in domains such as protein-protein interaction networks and brain functional connectivity.
Summary updated