Systems and Methods for 3D Data Visualization and Network Extraction

Abstract

Systems and methods for data visualization and network extraction in accordance with embodiments of the invention are illustrated. One embodiment includes a method including obtaining a graph comprising a plurality of nodes and a plurality of edges, identifying a plurality of communities in the graph, where each community includes nodes from the plurality of nodes, generating a community graph structure based on the identified communities, where the community graph includes a plurality of supernodes and a plurality of superedges, spatializing the community graph structure, unpacking the spatialized community graph structure into an unpacked graph structure comprising the plurality of nodes and the plurality of edges, where each node in the plurality of nodes is located at approximately the position of the supernode that represented it, spatializing the unpacked graph structure, and providing the spatialized unpacked graph structure.

What is claimed is: 
     
         1 . A data visualization system comprising:
 at least one processor; and   a memory, the memory containing a data visualization application, where the data visualization application directs the at least one processor to:
 obtain a graph comprising a plurality of nodes and a plurality of edges; 
 identify a plurality of communities in the graph, where each community comprises nodes from the plurality of nodes; 
 generate a community graph structure based on the identified communities;
 where the community graph comprises a plurality of supernodes and a plurality of superedges; 
 where each supernode in the plurality of supernodes represents nodes in the plurality of nodes being part of the same community; and 
 where each superedge in the plurality of superedges connects two supernodes, and represents edges in the plurality of edges connecting nodes represented by the two supernodes; 
 
 spatialize the community graph structure; 
 unpack the spatialized community graph structure into an unpacked graph structure comprising the plurality of nodes and the plurality of edges, where each node in the plurality of nodes is located at approximately the position of the supernode that represented it; 
 spatialize the unpacked graph structure; and 
 provide the spatialized unpacked graph structure. 
   
     
     
         2 . The data visualization system of  claim 1 , further comprising a display; and wherein the data visualization application further directs the at least one processor to provide the spatialized unpacked graph structure via the display. 
     
     
         3 . The data visualization system of  claim 1 , wherein to identify communities in the graph, the data visualization application further directs the at least one processor to:
 generate a plurality of community labels via application of Markov Clustering, where each node in the plurality of nodes is assigned a label from the plurality of community labels; and   refine the assignment of community labels via Louvain Modularity.   
     
     
         4 . The data visualization system of  claim 3 , wherein the at least one processor comprises at least one graphics processing unit (GPU) having a GPU memory, wherein a pruning threshold for the Markov Clustering is equal to the lesser of the number of nodes in the plurality of nodes and a size of the GPU memory×10 6 /50×the number of nodes in the plurality of nodes. 
     
     
         5 . The data visualization system of  claim 3 , wherein the Markov Clustering is applied for between 3 and 15 iterations. 
     
     
         6 . The data visualization system of  claim 1 , wherein the data visualization application further directs the at least one processor to approximate a centrality metric for each given community node in the spatialized unpacked graph structure by further directing the at least one processor to:
 randomly sample a portion of the plurality of nodes without replacement;   compute graph distance from each sampled node to each given community node in the spatialized unpacked graph structure;   randomly resample the remaining portion of the plurality of nodes without replacement and computing graph distance until a minimum sampling threshold is met and a processing time threshold is met; and   approximate at least one centrality metric for each node in the plurality of nodes based on the computed graph distances.   
     
     
         7 . The data visualization system of  claim 6 , wherein the minimum sampling threshold is 1024 nodes; and wherein the processing time threshold is 10 seconds. 
     
     
         8 . The data visualization system of  claim 1 , wherein to obtain the graph, the data visualization application further directs the at least one processor to:
 obtain a tabular data structure having a plurality of rows and a plurality of columns; and   convert the tabular data structure into a graph structure.   
     
     
         9 . The data visualization system of  claim 8 , wherein to convert the tabular data structure into a graph structure, the data visualization application directs the at least one processor to:
 identify a node column from the plurality of columns;   identify a plurality of associative columns from the plurality of columns;   generate a set of nodes based on values in the node column, where each node in the set of nodes represents a value in the node column without duplication;   construct a reverse index of the tabular data structure, where:
 the reverse index comprises a set of key-value pairs; 
 a key in a given key-value pair is a given value from the plurality of associative columns without duplication; and 
 a value in the given key-value pair is a list of values from the node column that appear on the same row as the given value from the plurality of associative columns without duplication; 
   construct a set of edges based on the reverse index, where each edge in the set of edges is constructed by connecting every combination of node values in the value of each key-value pair;   construct an edgelist from the set of edges, where the edgelist comprises a list of every edge in the set of edges;   replace edges in the edgelist having identical endpoints with a single edge, where a weight of the replacement edge is equal to the sum of edge weights of the replaced edges; and   construct a graph structure using edges in the edgelist to connect nodes in the set of nodes.   
     
     
         10 . The data visualization system of  claim 9 , wherein the data visualization application directs the at least one processor to prune the reverse index by removing key-value pairs having a length of the value greater than 10% of the size of the set of nodes. 
     
     
         11 . A data visualization method comprising:
 obtaining a graph comprising a plurality of nodes and a plurality of edges;   identifying a plurality of communities in the graph, where each community comprises nodes from the plurality of nodes;   generating a community graph structure based on the identified communities;
 where the community graph comprises a plurality of supernodes and a plurality of superedges; 
 where each supernode in the plurality of supernodes represents nodes in the plurality of nodes being part of the same community; and 
 where each superedge in the plurality of superedges connects two supernodes, and represents edges in the plurality of edges connecting nodes represented by the two supernodes; 
   spatializing the community graph structure;   unpacking the spatialized community graph structure into an unpacked graph structure comprising the plurality of nodes and the plurality of edges, where each node in the plurality of nodes is located at approximately the position of the supernode that represented it;   spatializing the unpacked graph structure; and   providing the spatialized unpacked graph structure.   
     
     
         12 . The data visualization method of  claim 11 , further comprising providing the spatialized unpacked graph structure via a display. 
     
     
         13 . The data visualization method of  claim 11 , wherein identifying communities in the graph comprises:
 generating a plurality of community labels via application of Markov Clustering, where each node in the plurality of nodes is assigned a label from the plurality of community labels; and   refining the assignment of community labels via Louvain Modularity.   
     
     
         14 . The data visualization method of  claim 3 , wherein a pruning threshold for the Markov Clustering is equal to the lesser of the number of nodes in the plurality of nodes and a size of a GPU memory×10 6 /50×the number of nodes in the plurality of nodes. 
     
     
         15 . The data visualization method of  claim 3 , wherein the Markov Clustering is applied for between 3 and 15 iterations. 
     
     
         16 . The data visualization method of  claim 11 , further comprising approximating a centrality metric for each given community node in the spatialized unpacked graph structure by:
 randomly sampling a portion of the plurality of nodes without replacement;   computing graph distance from each sampled node to each given community node in the spatialized unpacked graph structure;   randomly resampling the remaining portion of the plurality of nodes without replacement and computing graph distance until a minimum sampling threshold is met and a processing time threshold is met; and   approximating at least one centrality metric for each node in the plurality of nodes based on the computed graph distances.   
     
     
         17 . The data visualization method of  claim 16 , wherein the minimum sampling threshold is 1024 nodes; and wherein the processing time threshold is 10 seconds. 
     
     
         18 . The data visualization method of  claim 11 , wherein obtaining the graph comprises:
 obtaining a tabular data structure having a plurality of rows and a plurality of columns; and   converting the tabular data structure into a graph structure.   
     
     
         19 . The data visualization system of method  18 , wherein converting the tabular data structure into a graph structure comprises:
 identifying a node column from the plurality of columns;   identifying a plurality of associative columns from the plurality of columns;   generating a set of nodes based on values in the node column, where each node in the set of nodes represents a value in the node column without duplication;   constructing a reverse index of the tabular data structure, where:
 the reverse index comprises a set of key-value pairs; 
 a key in a given key-value pair is a given value from the plurality of associative columns without duplication; and 
 a value in the given key-value pair is a list of values from the node column that appear on the same row as the given value from the plurality of associative columns without duplication; 
   constructing a set of edges based on the reverse index, where each edge in the set of edges is constructed by connecting every combination of node values in the value of each key-value pair;   constructing an edgelist from the set of edges, where the edgelist comprises a list of every edge in the set of edges;   replacing edges in the edgelist having identical endpoints with a single edge, where a weight of the replacement edge is equal to the sum of edge weights of the replaced edges; and   constructing a graph structure using edges in the edgelist to connect nodes in the set of nodes.   
     
     
         20 . The data visualization method of  claim 19 , further comprising pruning the reverse index by removing key-value pairs having a length of the value greater than 10% of the size of the set of nodes.