Determination of graph connectivity metrics using bit-vectors
AssigneeUnisys Corporation
InventorGlenn C. Becker
Life of this patent
Estimating the term…
Abstract
Determination of a connectivity-metrics for graphs representative of networks of interest. A graph that represents a network of interest is accessed. The graph includes nodes representing points in the network of interest, and edges corresponding to the nodes. Bit-vectors are generated corresponding to the nodes and/or edges, wherein individual bits in the bit-vectors respectively provide a logical indication of connectedness. The connectivity-metric is then determined by applying a logical bit operation to the plurality of bit-vectors. Examples of connectivity metrics include a connected components, shortest paths, betweenness, clustering, and tree-based determinations.
Claims20
A method for determining a connectivity-metric for a graph representative of a network of interest, the method comprising:
- accessing a graph that represents a network of interest, the graph comprising a plurality of nodes representing points in the network of interest, and a plurality of edges corresponding to the plurality of nodes;
- generating a plurality of bit-vectors respectively corresponding to at least one of the plurality of nodes or the plurality of edges, wherein individual bits in the bit-vectors respectively provide a logical indication of connectedness;
- and
- determining the connectivity-metric by applying a logical bit operation to the plurality of bit-vectors;
- wherein the accessing, generating, and determining steps are performed on at least one particular machine, said at least one particular machine comprising at least one physical computing device.
2-4. (canceled)
7-8. (canceled)
A system for determining a connectivity-metric for a graph representative of a network of interest, the system comprising:
- at least one particular machine, said at least one particular machine comprising at least one physical computing device;
- wherein the at least one particular machine accesses a graph that represents a network of interest, the graph comprising a plurality of nodes representing points in the network of interest, and a plurality of edges corresponding to the plurality of nodes;
- a plurality of bit-vectors respectively corresponding to at least one of the plurality of nodes or the plurality of edges, wherein individual bits in the bit-vectors respectively provide a logical indication of connectedness, the plurality of bit-vectors being generated by the at least one particular machine;
- and
- a logical bit operation being applied by the at least one particular machine to the plurality of bit-vectors, wherein the connectivity metric is determined.
10-12. (canceled)
An apparatus for determining a connectivity-metric for a graph representative of a network of interest, the apparatus comprising:
- a graph management module, which accesses a graph that represents a network of interest, the graph comprising a plurality of nodes representing points in the network of interest, and a plurality of edges corresponding to the plurality of nodes;
- a bit-vector generation module, in communication with the graph management module, which generates a plurality of bit-vectors respectively corresponding to at least one of the plurality of nodes or the plurality of edges, wherein individual bits in the bit-vectors respectively provide a logical indication of connectedness;
- and
- a connectivity-metric determination module, in communication with the bit-vector generation module, which determines the connectivity-metric by applying a logical bit operation to the plurality of bit-vectors;
- wherein the graph management module, the bit-vector generation module, and the connectivity-metric determination module are executed on at least one particular machine, said at least one particular machine comprising at least one physical computing device.
16-18. (canceled)
A computer readable medium having stored thereon bit-vectors comprising:
- a first field containing data representing a bit-vector corresponding to a first node of a graph or a first edge of the graph, wherein the graph represents a network of interest;
- a second field containing data representing a second bit-vector corresponding to a second node of the graph or a second edge of the graph;
- and
- a third field containing data representing an updated bit-vector derived from the first and the second field, wherein a logical bit operation is applied to the first and second field and a connectivity-metric is determined,
- wherein the first field, the second field, and the third field are stored on at least one particular machine, said at least one particular machine comprising at least one physical computing device.
Dependencies are inferred from the claim text.