Decentralized graph clustering using the schrodinger equation
AssigneeRaytheon BBN Technologies Corp.
InventorsTuhin Sahai, Hari Kiran Krovi
Life of this patent
Estimating the term…
Abstract
A method for node cluster assignment in a graph includes identifying neighboring nodes of a first node in the graph, calculating one or more elements of a graph Laplacian of the graph, the one or more elements of the graph Laplacian corresponding to the first node and the neighboring nodes, initializing a first wavefunction associated with the first node with an initial value, evolving the first wavefunction associated with the first node over time based on the initial value, the one or more elements of the graph Laplacian, and previous states of wavefunctions of the neighboring nodes to generate a time-evolved wavefunction vector, and identifying a cluster assignment of the first node based on the time-evolved wavefunction vector.
Claims20
A method for node cluster assignment in a graph, the method comprising:
- identifying neighboring nodes of a first node in the graph;
- calculating one or more elements of a graph Laplacian of the graph, the one or more elements of the graph Laplacian corresponding to the first node and the neighboring nodes;
- initializing a first wavefunction associated with the first node with an initial value;
- evolving the first wavefunction associated with the first node over time based on the initial value, the one or more elements of the graph Laplacian, and previous states of wavefunctions of the neighboring nodes to generate a time-evolved wavefunction vector;
- and
- identifying a cluster assignment of the first node based on a spectrum of the time-evolved wavefunction vector.
A distributed computing system comprising:
- a plurality of computational nodes interconnected as a graph, a first node of the plurality of computational nodes comprising:
- a processor;
- and
- a processor memory local to the processor, wherein the processor memory has stored thereon instructions that, when executed by the processor, cause the processor to perform:
- identifying neighboring nodes of a first node from among the plurality of computational nodes;
- calculating one or more elements of a graph Laplacian of the graph, the one or more elements of the graph Laplacian corresponding to the first node and the neighboring nodes;
- initializing a first wavefunction associated with the first node with an initial value;
- evolving the first wavefunction associated with the first node over time based on the initial value, the one or more elements of the graph Laplacian, and previous states of wavefunctions of the neighboring nodes to generate a time-evolved wavefunction vector;
- and
- identifying a cluster assignment of the first node based on a spectrum of the time-evolved wavefunction vector.
Dependencies are inferred from the claim text.