Algorithms and Distribution-Free Models for Social and Information Networks
Abstract
Theoretical computer science has, over the past 40 years, developed a remarkably sophisticated toolbox for reasoning about and designing algorithms for well-motivated classes of graphs, such as planar graphs, bounded-treewidth graphs, and perfect graphs. Meanwhile, the past 10--15 years have seen the rise of large-scale social networks, such as the graphs defined by Facebook friendship relationships or followers on Twitter. The overarching goal of the proposed research is to define new graph classes relevant to the study of social networks, and to develop structural and algorithmic results for such graphs. More concretely, the project comprises three closely interrelated goals: definitions, structural results, and algorithms. 1. The first research goal is to develop definitions of graph classes motivated by triadic closure --- the idea that vertices with common neighbors are likely to be connected by an edge. There is tremendous empirical support for this property in social networks, and this property seems to lead to graph classes with more exploitable structure than the other most widely accepted properties of social networks, such as heavy-tailed degree distributions. 2. The second research goal is to develop structural results for the graph classes we define, to understand what these graphs ``look like. This is a familiar strategy for understanding restricted graph classes, analogous to using separator theorems to make precise how planar graphs resemble grids, tree decompositions to quantify how bounded-treewidth graphs resemble trees, and the regularity lemma to describe how dense graphs are approximately composed of ``random-like bipartite graphs. Such structural results are interesting in their own right and provide a flexible foundation for algorithmic applications. 3. The third research goal is to develop algorithms that solve problems more effectively for graphs in the proposed classes than for worst-case graphs. Empirically, many optimization problems that are notoriously difficult in the worst case, such as finding cliques or dense subgraphs, are solved to near-optimality in social networks by fast heuristics. Narrowing the gap between this theoretical intractability (in the worst case) and empirical tractability (in social networks) of these problems is a concrete and practically relevant challenge for algorithm analysis ``beyond the worst case. Specific opportunities include provably polynomial-time or fixed-parameter tractable algorithms for problems that are NP-hard in worst-case graphs; approximation algorithms with better approximation ratios for social networks than in the worst case; and algorithms for the approximate recovery of planted solutions.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- May 13, 2019
- Source ID
- W911NF1910294
Entities
People
- Seshadhri Comandur
Organizations
- Army Contracting Command
- United States Army
- University of California, Santa Cruz