Many real-world networks evolve over time, that is, new contacts appear and old contacts may disappear. They can be modeled as temporal graphs where interactions between vertices (which represent people in the case of social networks) are represented by time-stamped edges. One of the most fundamental problems in (social) network analysis is community detection, and one of the most basic primitives to model a community is a clique. Addressing the problem of finding communities in temporal networks, [TCS 2016] introduced @math -cliques as a natural temporal version of cliques. [SNAM 2017] showed how to adapt the well-known Bron-Kerbosch algorithm to enumerate @math -cliques. We continue this work and improve and extend the algorithm of to enumerate temporal @math -plexes (notably, cliques are the special case @math ). We define a @math - @math -plex as a set of vertices and a time interval, where during this time interval each vertex has in each consecutive @math time steps at least one edge to all but at most @math vertices in the chosen set of vertices. We develop a recursive algorithm for enumerating all maximal @math - @math -plexs and perform experiments on real-world social networks that demonstrate the practical feasibility of our approach. In particular, for the special case of @math -1-plexes (that is, @math -cliques), we observe that our algorithm is on average significantly faster than the previous algorithms by [SNAM 2017] and [IPL 2018] for enumerating @math -cliques.
Aside from community detection, many other problem areas also have been studied in the context of temporal graphs, including connectivity problems @cite_21 @cite_18 @cite_42 @cite_16 @cite_17 , graph exploration @cite_20 @cite_32 , clustering @cite_40 , and covering problems @cite_22 @cite_8 . For an extended overview on research related to temporal graphs, we refer to the surveys of Holme and Saram "aki @cite_33 , Casteigts and Flocchini @cite_1 @cite_15 , Michail @cite_29 , and @cite_30 .
@cite_30 @cite_18 @cite_22 @cite_33 @cite_8 @cite_29 @cite_21 @cite_42 @cite_32 @cite_1 @cite_40 @cite_15 @cite_16 @cite_20 @cite_17
2964196611 2835349798 2899533224 1881841366 2086991377 2461566632 2889043416 2903765129 2903724556 2792129212 2923258301 799990534 2884564598
Graph theory provides a language for studying the structure of relations, and it is often used to study interactions over time too. However, it poorly captures the intrinsically temporal and structural nature of interactions, which calls for a dedicated formalism. In this paper, we generalize graph concepts to cope with both aspects in a consistent way. We start with elementary concepts like density, clusters, or paths, and derive from them more advanced concepts like cliques, degrees, clustering coefficients, or connected components. We obtain a language to directly deal with interactions over time, similar to the language provided by graphs to deal with relations. This formalism is self-consistent: usual relations between different concepts are preserved. It is also consistent with graph theory: graph concepts are special cases of the ones we introduce. This makes it easy to generalize higher level objects such as quotient graphs, line graphs, k-cores, and centralities. This paper also considers discrete versus continuous time assumptions, instantaneous links, and extensions to more complex cases. In this work we consider temporal networks, i.e. networks defined by a labeling ( ) assigning to each edge of an underlying graphG a set of discrete time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on path problems of temporal networks. In particular, we consider time-respecting paths, i.e. paths whose edges are assigned by ( ) a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a natural analogue of Menger’s theorem holding for arbitrary temporal networks. Finally, we propose two cost minimization parameters for temporal network design. One is the temporality of G, in which the goal is to minimize the maximum number of labels of an edge, and the other is the temporal cost of G, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some connectivity constraint. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees. Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in stark contrast to practice where data is inherently dynamic and subject to discrete changes over time. A temporal graph is a graph whose edges are assigned a set of integer time labels, indicating at which discrete time steps the edge is active. In this paper we present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and a natural number ∆, we ask for a coloring sequence for each vertex such that (i) in every sliding time window of ∆ consecutive time steps, in which an edge is active, this edge is properly colored (i.e. its endpoints are assigned two different colors) at least once during that time window, and (ii) the total number of different colors is minimized. This sliding window temporal coloring problem abstractly captures many realistic graph coloring scenarios in which the underlying network changes over time, such as dynamically assigning communication channels to moving agents. We present a thorough investigation of the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. Some of our algorithms are linear-time fixed-parameter tractable with respect to appropriate parameters, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH). A temporal graph is, informally speaking, a graph that changes with time. When time is discrete and only the relationships between the participating entities may change and not the entities themselves, a temporal graph may be viewed as a sequence (G_1,G_2 ,G_l ) of static graphs over the same (static) set of nodes V. Though static graphs have been extensively studied, for their temporal generalization we are still far from having a concrete set of structural and algorithmic principles. Recent research shows that many graph properties and problems become radically different and usually substantially more difficult when an extra time dimension in added to them. Moreover, there is already a rich and rapidly growing set of modern systems and applications that can be naturally modeled and studied via temporal graphs. This, further motivates the need for the development of a temporal extension of graph theory. We survey here recent results on temporal graphs and temporal graph problems that have appeared in the Computer Science community. Many network problems are based on fundamental relationships involving time. Consider, for example, the problems of modeling the flow of information through a distributed network, studying the spread of a disease through a population, or analyzing the reachability properties of an airline timetable. In such settings, a natural model is that of a graph in which each edge is annotated with a time label specifying the time at which its endpoints "communicated." We will call such a graph a temporal network. To model the notion that information in such a network "flows" only on paths whose labels respect the ordering of time, we call a path time-respecting if the time labels on its edges are non-decreasing. The central motivation for our work is the following question: how do the basic combinatorial and algorithmic properties of graphs change when we impose this additional temporal condition? The notion of a path is intrinsic to many of the most fundamental algorithmic problems on graphs; spanning trees, connectivity, flows, and cuts are some examples. When we focus on time-respecting paths in place of arbitrary paths, many of these problems acquire a character that is different from the traditional setting, but very rich in its own right. We provide results on two types of problems for temporal networks. First, we consider connectivity problems, in which we seek disjoint time-respecting paths between pairs of nodes. The natural analogue of Menger's Theorem for node-disjoint paths fails in general for time-respecting paths; we give a non-trivial characterization of those graphs for which the theorem does hold in terms of an excluded subdivision theorem, and provide a polynomial-time algorithm for connectivity on this class of graphs. (The problem on general graphs is NP-complete.) We then define and study the class of inference problems, in which we seek to reconstruct a partially specified time labeling of a network in a manner consistent with an observed history of information flow. We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u to vertex v is a path from u to v where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a (u, v)-journey for any pair of vertices u, v, u ź v. We first give a simple polynomial-time algorithm to check whether a given temporal graph is temporally connected. We then consider the case in which a designer of temporal graphs can freely choose availability instances for all edges and aims for temporal connectivity with very small cost; the cost is the total number of availability instances used. We achieve this via a simple polynomial-time procedure which derives designs of cost linear in n. We also show that the above procedure is (almost) optimal when the underlying graph is a tree, by proving a lower bound on the cost for any tree. However, there are pragmatic cases where one is not free to design a temporally connected graph anew, but is instead given a temporal graph design with the claim that it is temporally connected, and wishes to make it more cost-efficient by removing labels without destroying temporal connectivity (redundant labels). Our main technical result is that computing the maximum number of redundant labels is APX-hard, i.e., there is no PTAS unless P = NP. On the positive side, we show that in dense graphs with random edge availabilities, there is asymptotically almost surely a very large number of redundant labels. A temporal design may, however, be minimal, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least nlogn labels. The number of telecommunication networks deployed in a dynamic environment is quickly growing. This trend exists both in everyday life (e.g., smartphones, vehicles, and commercial satellites) and in a military context (e.g., dismounted soldiers or swarms of UAVs). Unfortunately, few theoretical tools to date have enabled the study of dynamic networks in a formal and rigorous way. As a result, it is hard and sometimes impossible to guarantee, mathematically, that a given algorithm will reach its objectives once deployed in real conditions. In this report, we identify a collection of recent theoretical tools whose purpose is to model, describe, and leverage dynamic networks in a formal way. These tools include a dynamic graph formalism, various computational models, and communication models for distributed networks. We extend many graph theoretical concepts towards a dynamic variant and show how these new variants impact the solution of classical distributed problems. The report also presents a hierarchy of dynamic networks based on dynamic graph properties, thereby offering a combinatorial alternative to the well-known mobility models typically used in simulations. Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-Layer Cluster Editing we receive a set of graphs on the same vertex set, called layers and aim to transform all layers into cluster graphs (disjoint unions of cliques) that differ only slightly. More specifically, we want to mark at most d vertices and to transform each layer into a cluster graph using at most k edge additions or deletions per layer so that, if we remove the marked vertices, we obtain the same cluster graph in all layers. In Temporal Cluster Editing we receive a sequence of layers and we want to transform each layer into a cluster graph so that consecutive layers differ only slightly. That is, we want to transform each layer into a cluster graph with at most k edge additions or deletions and to mark a distinct set of d vertices in each layer so that each two consecutive layers are the same after removing the vertices marked in the first of the two layers. We study the combinatorial structure of the two problems via their parameterized complexity with respect to the parameters d and k, among others. Despite the similar definition, the two problems behave quite differently: In particular, Multi-Layer Cluster Editing is fixed-parameter tractable with running time k^ O(k + d) s^ O(1) for inputs of size s, whereas Temporal Cluster Editing is W[1]-hard with respect to k even if d = 3. The number of telecommunication networks deployed in a dynamic environment is quickly growing. This is true in our everyday life (e.g., smartphones, vehicles, or satellites) as well as in the military context (e.g., dismounted soldiers or swarms of UAVs). Unfortunately, few theoretical tools enable, to date, the study of dynamic networks in a formal and rigorous way. As a result, it is hard and sometimes impossible to guarantee, mathematically, that a given algorithm will reach its objectives once deployed in real conditions. Having such guarantees would seem to be crucial in a military context. In a previous report we identified a collection of recent theoretical tools whose purpose is to model, describe, and leverage dynamic networks in a formal way. This report focuses on problems, algorithms, and analysis techniques. We review recent efforts towards the design and analysis of distributed algorithms in dynamic networks, with an emphasis on those results that are of a deterministic and analytical nature. The topics include a discussion on how mobility impacts the very definition of problems; a set of generic tools to be used in the design or analysis of dynamic network algorithms; a discussion on the impact of various types of dynamics on the feasibility and complexity of given problems; a classification of dynamic networks based on dynamic graph properties; and finally, a discussion on how real-world mobility contexts relate to some of these classes. Abstract We investigate for temporal graphs the computational complexity of separating two distinct vertices s and z by vertex deletion. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal ( s , z ) -Separation problem is NP -complete, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph—there we observe polynomial-time solvability in the case of bounded treewidth—as well as restrictions concerning the “temporal evolution” along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases. A temporal graph is a graph in which the edge set can change from step to step. The temporal graph exploration problem TEXP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. We consider only temporal graphs that are connected at each step. For such temporal graphs with n nodes, we show that it is ( NP )-hard to approximate TEXP with ratio (O(n^ 1- ) ) for any ( >0 ). We also provide an explicit construction of temporal graphs that require ( (n^2) ) steps to be explored. We then consider TEXP under the assumption that the underlying graph (i.e. the graph that contains all edges that are present in the temporal graph in at least one step) belongs to a specific class of graphs. Among other results, we show that temporal graphs can be explored in (O(n^ 1.5 k^2 n) ) steps if the underlying graph has treewidth k and in (O(n ^3 n) ) steps if the underlying graph is a (2 n ) grid. We also show that sparse temporal graphs with regularly present edges can always be explored in O(n) steps. Temporal graphs are graphs with time-stamped edges. We study the problem of finding a small vertex set (the separator) with respect to two designated terminal vertices such that the removal of the set eliminates all temporal paths connecting one terminal to the other. Herein, we consider two models of temporal paths: paths that pass through arbitrarily many edges per time step (non-strict) and paths that pass through at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-hardness versus polynomial-time solvability) for both problem variants. Moreover we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. We further show that, on temporal graphs with planar underlying graph, if additionally the number of time steps is constant, then the problem variant for strict paths is solvable in quasi-linear time. Finally, we introduce and motivate the notion of a temporal core (vertices whose incident edges change over time). We prove that the non-strict variant is fixed-parameter tractable when parameterized by the size of the temporal core, while the strict variant remains NP-complete, even for constant-size temporal cores.