Compressing and Analyzing Large-Scale Networks
DescriptionNetworks (or graphs) are powerful and expressive mathematical tools for modeling and analyzing social, economic, biological, and technological systems. Real-world networks can be extremely large to the order of millions of entities and billions of connections between them. Such massive networks are challenging to store and analyze. We have developed algorithms which (i) compress networks by replacing specific structures in the network with a smaller representation and (ii) leverage the unique properties of the structures to analyze the networks in their compressed form. Compression reduces the time for analysis. We present results for the storage and time reduction our algorithms offer for finding the Closeness Centrality of nodes in compressed graphs versus in their standard, uncompressed representation. Our algorithms can reduce the size of certain networks by 90% and lower the time to find the Closeness Centrality of their nodes by 80 - 99%.