Extended Abstract: K-Truss Implementation in Arkouda

Authors:

Joseph Patchett, Zhihui Du, David Bader

Abstract

The k-Truss algorithm is the decomposition of a graph into cliques where every edge is incident to k − 2 triangles. The results of this decomposition have implications in national security, social media, and community identification. These results can be used to interpret how connected a community is e.g. how interconnected a group on social media is. Higher values of k imply a higher degree of connection. The maximal k-truss is the subgraph for which there is the largest k. For certain graphs like those in social media the maximal k-Truss is not informative, therefore our algorithm allows different choices of k to tailor to the needs of each use case. Our implementation of the k-Truss algorithm in Arkouda finds all maximal k-trusses in a graph. Arkouda [1], [2] is an open-source framework for large scale graph analytics that allows users to access a powerful server driven backend from their own personal computer. Real-world data and the graphs resulting from that data have become increasingly complex. Arkouda utilizes a powerful Chapel [3] back-end, ZeroMQ [4] for message communication, and a Python [5] front-end for users. Computations that require complex calculations and large networks will be handled on the backend abstracted from the user. Our major contribution is extending the abilities of Arkouda and k-truss is a typical graph algorithm for such a framework.