More Like this

1. Truss Analytics Algorithms and Integration in Arkouda

   Du, Zhihui; Patchett, Joseph; Rodriguez, Oliver Alvarado; Bader, David A; Merrill, Michael; Reus, William (June 2022, The 9th Annual Chapel Implementers and Users Workshop)

   The K-Truss of a graph is a cohesive subgraph that has been widely used for community detection in applications such as social networks and security analysis. In this paper, we first propose one optimized triangle search kernel with a few operations that can be used in both triangle counting and triangle search to replace the existing list intersection method. Based on the optimized kernel, three truss analytics algorithms, an optimized K-Truss parallel algorithm, a maximal K-Truss parallel algorithm, and a Truss decomposition parallel algorithm, are developed to efficiently enable different kinds of graph analysis. Moreover, all proposed parallel algorithms have been implemented in the highly-productive parallel language Chapel and integrated into the open-source framework Arkouda. Experimental results compared with the existing list intersection-based method show that for both synthetic and real-world graphs, the proposed method can significantly improve the performance of truss analysis on large graphs. The implemented method is publicly available from GitHub. 

   more » « less
2. High-Performance Truss Analysis in Arkouda

   Zhihui Du; Joseph Patchett; Oliver Alvarado Rodriguez; David A. Bader (December 2022, The 29th IEEE International Conference on High Performance Computing, Data, and Analytics (HiPC))

   In graph analytics, a truss is a cohesive subgraph based on the number of triangles supporting each edge. It is widely used for community detection applications such as social networks and security analysis, and the performance of truss analytics highly depends on its triangle counting method. This paper proposes a novel triangle counting kernel named Minimum Search (MS). Minimum Search can select two smaller adjacency lists out of three and uses fine-grained parallelism to improve the performance of triangle counting. Then, two basic algorithms, MS-based triangle counting, and MS-based support updating are developed. Based on the novel triangle counting kernel and the two basic algorithms above, three fundamental parallel truss analytics algorithms are designed and implemented to enable different kinds of graph truss analysis. These truss algorithms include an optimized K-Truss algorithm, a Max-Truss algorithm, and a Truss Decomposition algorithm. Moreover, all proposed algorithms have been implemented in the parallel language Chapel and integrated into an open-source framework, Arkouda. Through Arkouda, data scientists can efficiently conduct graph analysis through an easy-to-use Python interface and handle large-scale graph data in powerful back-end computing resources. Experimental results show that the proposed methods can significantly improve the performance of truss analysis on real-world graphs compared with the existing and widely adopted list intersection-based method. The implemented code is publicly available from GitHub (https://github.com/Bears-R-Us/arkoudanjit). } 

   more » « less
3. Truss-based Community Search: a Truss-equivalence Based Indexing Approach

   Akbas, Esra; Zhao, Peixiang (January 2017, Proceedings of the VLDB Endowment)

   We consider the community search problem defined upon a large graph G: given a query vertex q in G, to find as output all the densely connected subgraphs of G, each of which contains the query v. As an online, query-dependent variant of the well-known community detection problem, community search enables personalized community discovery that has found widely varying applications in real-world, large-scale graphs. In this paper, we study the community search problem in the truss-based model aimed at discovering all dense and cohesive k-truss communities to which the query vertex q belongs. We introduce a novel equivalence relation, k-truss equivalence, to model the intrinsic density and cohesiveness of edges in k-truss communities. Consequently, all the edges of G can be partitioned to a series of k-truss equivalence classes that constitute a space-efficient, truss-preserving index structure, EquiTruss. Community search can be henceforth addressed directly upon EquiTruss without repeated, time-demanding accesses to the original graph, G, which proves to be theoretically optimal. In addition, EquiTruss can be efficiently updated in a dynamic fashion when G evolves with edge insertion and deletion. Experimental studies in real-world, large-scale graphs validate the efficiency and effectiveness of EquiTruss, which has achieved at least an order of magnitude speedup in community search over the state-of-the-art method, TCP-Index. 

   more » « less
4. Optimizing Truss Structures Using Composite Materials under Natural Frequency Constraints with a New Hybrid Algorithm Based on Cuckoo Search and Stochastic Paint Optimizer (CSSPO)

   https://doi.org/10.3390/buildings13061551  

   Khodadadi, Nima; Harati, Ehsan; De Caso, Francisco; Nanni, Antonio (June 2023, Buildings)

   This article highlights the absence of published paradigms hybridized by The Cuckoo Search (CS) and Stochastic Paint Optimizer (SPO) for optimizing truss structures using composite materials under natural frequency constraints. The article proposes a novel optimization algorithm called CSSPO for optimizing truss structures made of composite materials, known as fiber-reinforced polymer (FRP) composites, to address this gap. Optimization problems of truss structures under frequency constraints are recognized as challenging due to their non-linear and non-convex search spaces that contain numerous local optima. The proposed methodology produces high-quality optimal solutions with less computational effort than the original methods. The aim of this work is to compare the performance of carbon FRP (CFRP), glass FRP (GFRP), and steel using a novel hybrid algorithm to provide valuable insights and inform decision-making processes in material selection and design. Four benchmark structure trusses with natural frequency constraints were utilized to demonstrate the efficiency and robustness of the CSSPO. The numerical analysis findings indicate that the CSSPO outperforms the classical SPO and exhibits comparable or superior performance when compared to the SPO. The study highlights that implementing CFRP and GFRP composites in truss construction leads to a notable reduction in weight compared to using steel. 

   more » « less
5. Topology Optimization of Lightweight Structures With Application to Bone Scaffolds and 3D Printed Shoes for Diabetics

   https://doi.org/10.1115/1.4053396  

   Wang, Zhujiang; Srinivasa, Arun; Reddy, J. N.; Dubrowski, Adam (April 2022, Journal of Applied Mechanics)

   Abstract An automatic complex topology lightweight structure generation method (ACTLSGM) is presented to automatically generate 3D models of lightweight truss structures with a boundary surface of any shape. The core idea of the ACTLSGM is to use the PIMesh, a mesh generation algorithm developed by the authors, to generate node distributions inside the object representing the boundary surface of the target complex topology structures; raw lightweight truss structures are then generated based on the node distributions; the resulting lightweight truss structure is then created by adjusting the radius of the raw truss structures using an optimization algorithm based on finite element truss analysis. The finite element analysis-based optimization algorithm can ensure that the resulting structures satisfy the design requirements on stress distributions or stiffness. Three demos, including a lightweight structure for a cantilever beam, a femur bone scaffold, and a 3D shoe sole model with adaptive stiffness, can be used to adjust foot pressure distributions for patients with diabetic foot problems and are generated to demonstrate the performance of the ACTLSGM. The ACTLSGM is not limited to generating 3D models of medical devices, but can be applied in many other fields, including 3D printing infills and other fields where customized lightweight structures are required. 

   more » « less