Content not yet available
This lecture has no active video or poster.
keywords:
other foundations of search optimization
so
A graph $G$ is $c$-closed if any two vertices with at least $c$ common neighbors are adjacent to each other. Introduced by Fox, Roughgarden, Seshadhri, Wei and Wein ICALP 2018, SICOMP 2020, this definition is an abstraction of the triadic closure property exhibited by many real-world social networks, namely, friends of friends tend to be friends themselves. Social networks, however, are temporal rather than static---the connections change over a period of time. And hence temporal graphs, rather than static graphs, are often better suited to model social networks. Motivated by this, we introduce a definition of temporal $c$-closed graphs, in which if two vertices $u$ and $v$ have at least $c$ common neighbors during a short interval of time, then $u$ and $v$ are adjacent to each other around that time. Our pilot experiments show that several real-world temporal networks are indeed $c$-closed for rather small values of $c$. We also study the computational problems of enumerating maximal cliques and similar dense subgraphs in temporal $c$-closed graphs; a clique in a temporal graph is a subgraph that lasts for a certain period of time, during which every possible edge in the subgraph becomes active often enough, and other dense subgraphs are defined similarly. We bound the number of such maximal dense subgraphs, and thus show that the corresponding enumeration problems admit efficient algorithms, provided the graph evolves slowly over time; by slow evolution, we mean that between consecutive time-steps, the local change in adjacencies remains small. Our work also adds to a growing body of literature on defining suitable structural parameters for temporal graphs that can be leveraged to design efficient algorithms.
