The National Science Foundation Division of Computing and Communication Foundations awarded $600,000 under the Computer and Information Science and Engineering federal grant program (CFDA 47.070) to the Regents of the University of Michigan for a project grant titled "SMALL: Efficient Representation of Large Networks." The University of Michigan will develop new mathematical and algorithmic methods for graph sketching to more efficiently analyze very large networks, such as those representing the internet or social networks, which current algorithms struggle to handle due to their immense size. Specifically, the university will evaluate the effectiveness of graph spanners for representing shortest path distances; classify problems where more sophisticated data structures can outperform simpler sketching methods like subgraphs; and identify key structural graph properties that determine the difficulty of building sketches. The research draws upon methods from graph algorithms, extremal graph theory, information theory, and discrete geometry. The project aims to enable cheaper, faster, and more accessible analysis of modern networks with billions of nodes.
Generated 1/6/24, 1:06 PM