Determination of graph connectivity metrics using bit-vectors
View Patent ↗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.
1. 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 connectivity-metric is a clustering determination, and determining the connectivity-metric comprises using the plurality of bit-vectors to determine a clustering coefficient of a clustering algorithm;
wherein the clustering coefficient is defined as three times the number of triangles within the graph divided by all possible triples;
wherein triangles are defined as the number of fully connected groups of three nodes and triples are defined as nodes that are directly connected to two distinct other nodes; and
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. The method of claim 1 , wherein the plurality of bit-vectors respectively correspond to at least one of the plurality of nodes.
3. The method of claim 1 , wherein the plurality of bit-vectors respectively correspond to at least one of the plurality of edges.
4. 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;
wherein the connectivity-metric is a clustering determination, and determining the connectivity-metric comprises using the plurality of bit-vectors to determine a clustering coefficient of a clustering algorithm;
wherein the clustering coefficient is defined as three times the number of triangles within the graph divided by all possible triples;
wherein triangles are defined as the number of fully connected groups of three nodes and triples are defined as nodes that are directly connected to two distinct other nodes.
5. The system of claim 4 , wherein the plurality of bit-vectors respectively correspond to at least one of the plurality of nodes.
6. The system of claim 4 , wherein the plurality of bit-vectors respectively correspond to at least one of the plurality of edges.
7. 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 connectivity-metric is a clustering determination, and determining the connectivity-metric comprises using the plurality of bit-vectors to determine a clustering coefficient of a clustering algorithm;
wherein the clustering coefficient is defined as three times the number of triangles within the graph divided by all possible triples;
wherein triangles are defined as the number of fully connected groups of three nodes and triples are defined as nodes that are directly connected to two distinct other nodes;
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.
8. The apparatus of claim 7 , wherein the plurality of bit-vectors respectively correspond to at least one of the plurality of nodes.
9. The apparatus of claim 7 , wherein the plurality of bit-vectors respectively correspond to at least one of the plurality of edges.