K-core and k-truss algorithms assist with community search in large graphs and are used to identify cohesive portions of a graph based on specific metrics, particularly in mining applications. Discovering dense subgraphs is an essential task in graph mining, and is valuable in the analysis of social networks, biology, and identifying crime rings. Both algorithms proceed by iteratively removing components that do not meet a specified metric to produce a subgraph. By removing extraneous components, a user of the algorithm can produce simplified versions of large, complex graphs to provide clarity and understandability. Cohesive subgraphs allow the user to identify significant connections within their graph without a great deal of computational requirements.
A k-core represents the graph at different levels of granularity. It finds the largest subgraph in which all nodes are adjacent to at least k other nodes, i.e., all nodes have a minimum degree of at least k. For example, if the user is trying to find the 3-core of their graph, all nodes with less than three edges branching from them would be excluded. The standard k-core algorithm quantifies the significance of a node, with respect to its neighbors, by defining how connected it is.
A graph’s k-truss is the maximal induced subgraph in which all edges are incident to at least (k-2) triangles within the subgraph. A k-truss is basically a subgraph composed solely of triangles, which provides significant stability.
As the number k increases, fewer of the graph’s components remain in the resulting subgraph, leaving only the nodes and edges that form the most relevant structures of the graph. Researchers introduced these concepts while studying the clustering structure of social networks and describing the evolution of random graphs. They have also applied the concept in bioinformatics, network visualization, and resilience of networks in ecology. When dealing with huge graphs, the amount of time it takes to run computations is limiting, but by creating a more concise, structured version of a graph, users can more easily begin to analyze their data.
This post concludes our series to provide a deeper understanding of algorithms in the Katana Graph Python Library. Katana Graph, in collaboration with Intel, designed and made available this high-performance, easy-to-use graph analytics Python library.
Katana Graph fuses business-ready analytics, cutting-edge research, and scientific precision, and is devoted to real-world problem solving. We are relentless in our pursuit of faster and more efficient solutions to the most timely business challenges. Continuous improvement is the very foundation of our success. To learn how Katana Graph can solve your data problems, speak to a Katana Graph Intelligence Platform expert.
