Abstract
Clique identification includes the identification of node subsets within a larger graph that exhibit correlation or connectivity and has several applications. For example, a determination that N users are in close geographical proximity (or part of the same physical crowd) can be used for local, spatially targeted surfacing of advertisements. This disclosure describes techniques for fast clique identification within graphs that leverage the fact that identifying a spanning tree in a fully connected graph suffices to confirm a network clique. Nodes are indexed in the order they upload to a server (raster-scanning order). Pairwise correlations between nodes are computed on the go, thereby avoiding the computational bottleneck presented by the data upload of the last (fourth) node. Effectively, the techniques attempt to process first-in node information by leveraging spanning-tree properties.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Recommended Citation
n/a, "Fast Identification of Clique Patterns in a Data Network", Technical Disclosure Commons, (March 13, 2023)
https://www.tdcommons.org/dpubs_series/5736