Search

Given a network of Twitter users, can we capture their posting behavior over time, identify patterns that could probably describe, model or predict their activity? Can we identify temporal connectivity patterns that emerge from the use of specific attributes? More challengingly, are there particular attribute usage patterns which indicate an inherent anomaly? This work provides solid answers to all these questions, extending previous work employed on other social networks and attribute types. We propose TG-OUT, a pipeline of methods which : (a) model the temporal evolution of attribute induced graphs to detect peculiar attributes, (b) identify temporal patterns in attribute distributions, (c) investigate differences in patterns emerging from bot and/or non-bot accounts, (d) extract tailored sets of exploitable features. Experimental results show that: most of the individual attribute distributions remain stable over time following mostly power laws norm; the temporal evolution of attribute induced graphs obey certain laws and deviations are outliers; we discover that patterns present deviations which depend on the type of accounts which use each attribute; finally, we show that careful selection of only two features which are used to train a simple machine learning algorithm, produces a model which efficiently identifies attributes mainly used by bots. [ABSTRACT FROM AUTHOR]

In the study of temporal graphs, only paths respecting the flow of time are relevant. In this context, many concepts of walk disjointness have been proposed over the years and the validity of Menger's Theorem, as well as the complexity of related problems, have been investigated. Menger's Theorem states that the maximum number of vertex/edge disjoint paths between two vertices equals the minimum number of vertices/edges required to disconnect them. This paper introduces and investigates a type of disjointness that is only time-dependent. Two walks are said to be snapshot disjoint if they do not use edges active in the same snapshot. The related paths and cut problems are then defined and proved to be W[1]-hard and XP-time solvable when parameterized by the solution size. Additionally, in the light of the definition of Mengerian graphs given by Kempe, Kleinberg, and Kumar in their seminal paper (STOC'2000), we define a snapshot Mengerian graph as a graph G for which there is no time labeling for its edges where Menger's Theorem does not hold in the context of snapshot disjointness. We then characterize Mengerian graphs in terms of forbidden structures and provide a polynomial-time recognition algorithm. All our proofs work on the strict and the non-strict cases. Finally, we also present results about problems defined by similar types of disjointness, namely, multiedge disjointness and departure time disjointness. • A novel type of temporal paths disjointness. • Introduction of related parameters: maximum number of snapshot disjoint paths and minimum size of a snapshot cut. • Tight classification of related problems when parameterized by solution size. • Characterization and polynomial-time recognition of s-Mengerian graphs. • Comparison between parameters and "Mengerian" classes of graphs. [ABSTRACT FROM AUTHOR]

In multistage perfect matching problems, we are given a sequence of graphs on the same vertex set and are asked to find a sequence of perfect matchings, corresponding to the sequence of graphs, such that consecutive matchings are as similar as possible. More precisely, we aim to maximize the intersections, or minimize the unions between consecutive matchings. We show that these problems are NP-hard even in very restricted scenarios. As our main contribution, we present the first non-trivial approximation algorithms for these problems: On the one hand, we devise a tight approximation on graph sequences of length two (2-stage graphs). On the other hand, we propose several general methods to deduce multistage approximations from blackbox approximations on 2-stage graphs. [ABSTRACT FROM AUTHOR]

Abstract Directed Graph based models of a blockchain that capture accounts as nodes and transactions as edges, evolve over time. This temporal nature of a blockchain model enables us to understand the behavior (malicious or benign) of the accounts. Predictive classification of accounts as malicious or benign could help users of the permissionless blockchain platforms to operate in a secure manner. Motivated by this, we introduce temporal features such as burst and attractiveness on top of several already used graph properties such as the node degree and clustering coefficient. Using identified features, we train various Machine Learning (ML) models and identify the algorithm that performs the best in detecting malicious accounts. We then study the behavior of the accounts over different temporal granularities of the dataset before assigning them malicious tags. For the Ethereum blockchain, we identify that for the entire dataset—the ExtraTreesClassifier performs the best among supervised ML algorithms. On the other hand, using cosine similarity on top of the results provided by unsupervised ML algorithms such as K-Means on the entire dataset, we were able to detect 554 more suspicious accounts. Further, using behavior change analysis for accounts, we identify 814 unique suspicious accounts across different temporal granularities.

The NP-complete Vertex Cover problem asks to cover all edges of a graph by a small (given) number of vertices. It is among the most prominent graph-algorithmic problems. Following a recent trend in studying temporal graphs (a sequence of graphs, so-called layers, over the same vertex set but, over time, changing edge sets), we initiate the study of Multistage Vertex Cover. Herein, given a temporal graph, the goal is to find for each layer of the temporal graph a small vertex cover and to guarantee that two vertex cover sets of every two consecutive layers differ not too much (specified by a given parameter). We show that, different from classic Vertex Cover and some other dynamic or temporal variants of it, Multistage Vertex Cover is computationally hard even in fairly restricted settings. On the positive side, however, we also spot several fixed-parameter tractability results based on some of themost natural parameterizations. [ABSTRACT FROM AUTHOR]

A temporal graph is a pair (G , λ) where G is a simple graph and λ is a function assigning to each edge time labels telling at which snapshots each edge is active. As recently defined by Mertzios, Molter and Zamaraev (2021), a temporal coloring of (G , λ) is a sequence of colorings of the vertices of the snapshots such that each edge is properly colored at least once. We first focus on t-persistent and t-occurrent temporal graphs. The former (resp. the latter) are temporal graphs where each edge of G stays active for at least t consecutive (resp. not-necessarily consecutive) snapshots. We study which values of t make the problem polynomial-time solvable. We also investigate the complexity of the problem when restricted to temporal graphs (G , λ) such that G has bounded treewidth. [ABSTRACT FROM AUTHOR]

The closeness centrality of a vertex in a classical static graph is the reciprocal of the sum of the distances to all other vertices. However, networks are often dynamic and change over time. Temporal distances take these dynamics into account. In this work, we consider the harmonic temporal closeness with respect to the shortest duration distance. We introduce an efficient algorithm for computing the exact top-k temporal closeness values and the corresponding vertices. The algorithm can be generalized to the task of computing all closeness values. Furthermore, we derive heuristic modifications that perform well on real-world data sets and drastically reduce the running times. For the case that edge traversal takes an equal amount of time for all edges, we lift two approximation algorithms to the temporal domain. The algorithms approximate the transitive closure of a temporal graph (which is an essential ingredient for the top-k algorithm) and the temporal closeness for all vertices, respectively, with high probability. We experimentally evaluate all our new approaches on real-world data sets and show that they lead to drastically reduced running times while keeping high quality in many cases. Moreover, we demonstrate that the top-k temporal and static closeness vertex sets differ quite largely in the considered temporal networks. [ABSTRACT FROM AUTHOR]

Computing path queries such as the shortest path in public transport networks is challenging because the path costs between nodes change over time. A reachability query from a node at a given start time on such a network retrieves all points of interest (POIs) that are reachable within a given cost budget. Reachability queries are essential building blocks in many applications, for example, group recommendations, ranking spatial queries, or geomarketing. We propose an efficient solution for reachability queries in public transport networks. Currently, there are two options to solve reachability queries. (1) Execute a modified version of Dijkstra's algorithm that supports time-dependent edge traversal costs; this solution is slow since it must expand edge by edge and does not use an index. (2) Issue a separate path query for each single POI, i.e., a single reachability query requires answering many path queries. None of these solutions scales to large networks with many POIs. We propose a novel and lightweight reachability index. The key idea is to partition the network into cells. Then, in contrast to other approaches, we expand the network cell by cell. Empirical evaluations on synthetic and real-world networks confirm the efficiency and the effectiveness of our index-based reachability query solution. [ABSTRACT FROM AUTHOR]

Task‐based execution of graph workloads allows various ordered and unordered implementations, with tasks representing dependencies between graph vertices and edges. This work explores graph algorithms in the context of ordered and unordered task‐based implementations, that trade‐off work‐efficiency with parallelism. The monotonicity of convergent graph solutions is the reason behind the trade‐off between work‐efficiency and parallelism. This trade‐off results in variable performance‐based choices within and across different machines (CPUs and GPUs), graph algorithms, implementations (ordered, relaxed, and unordered). Input graphs also augment this choice space, with this work analyzing temporally changing graphs in addition to the static graphs explored by prior works. These algorithmic and architectural choices are first explored in this work, and it is seen that different graph workload‐input combinations perform optimally on diverse architectural configurations. The resulting choice space is analyzed and this work represents it in the form of characteristic variables that correlate with each choice space. Using these characteristic variables, this work proposes analytical and neural network models to correlate these choice spaces to find the best performing implementation. The variables and the prediction models proposed in this work are also integrated with a state‐of‐the‐art performance predictor on a multiaccelerator setup, and shows geometric performance gains of 54% on a CPU, 14% on a GPU, and 31.5% in a multiaccelerator setup over baseline implementations without performance prediction. [ABSTRACT FROM AUTHOR]

In this paper we present a graph-based framework that, utilizing relations between groups of System-calls, detects whether an unknown software sample is malicious or benign, and classifies a malicious software to one of a set of known malware families. In our approach we propose a novel graph representation of dependency graphs by capturing their structural evolution over time constructing sequential graph instances, the so-called Temporal Graphs. The partitions of the temporal evolution of a graph defined by specific time-slots, results to different types of graphs representations based upon the information we capture across the capturing of its evolution. The proposed graph-based framework utilizes the proposed types of temporal graphs computing similarity metrics over various graph characteristics in order to conduct the malware detection and classification procedures. Finally, we evaluate the detection rates and the classification ability of our proposed graph-based framework conducting a series of experiments over a set of known malware samples pre-classified into malware families. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be an undirected graph on n vertices and λ : E → 2 N a mapping that assigns to every edge a non-empty set of integer labels (discrete times when the edge is present). Such a labelled graph G = (G , λ) is temporally connected if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar [17] asked whether, given such a temporally connected graph, a sparse subset of edges always exists whose labels suffice to preserve temporal connectivity – a temporal spanner. Axiotis and Fotakis [5] answered negatively by exhibiting a family of Θ (n 2) -dense temporal graphs which admit no temporal spanner of density o (n 2). In this paper, we give the first positive answer as to the existence of o (n 2) -sparse spanners in a dense class of temporal graphs, by showing (constructively) that if G is a complete graph, then one can always find a temporal spanner with O (n log ⁡ n) edges. [ABSTRACT FROM AUTHOR]

Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration Δ , referred to as Δ -restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the "restless variant" of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the distance to disjoint path of the underlying graph, which implies W[1]-hardness for many other parameters like feedback vertex number and pathwidth. A natural question is thus whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work. [ABSTRACT FROM AUTHOR]

We consider the influence maximization problem over a temporal graph. We deviate from the standard model of influence maximization, where the goal is to choose the most influential vertices. In our model, we are given a fixed vertex and the goal is to find the best time steps to transmit so that the influence of this vertex is maximized. We frame this problem as a spreading process that follows a variant of the susceptible-infected-susceptible (SIS) model and focus on four objective functions. In the MaxSpread objective, the goal is to maximize the number of vertices that get infected at least once. In MaxViral and MaxViralTstep , the goal is to maximize the number of vertices that are infected at the same time step and at a given time step, respectively. Finally, in MinNonViralTime , the goal is to maximize the number of vertices that are infected in every d time-step window. [ABSTRACT FROM AUTHOR]

Abstract Similarity measures are used extensively in machine learning and data science algorithms. The newly proposed graph Relative Hausdorff (RH) distance is a lightweight yet nuanced similarity measure for quantifying the closeness of two graphs. In this work we study the effectiveness of RH distance as a tool for detecting anomalies in time-evolving graph sequences. We apply RH to cyber data with given red team events, as well to synthetically generated sequences of graphs with planted attacks. In our experiments, the performance of RH distance is at times comparable, and sometimes superior, to graph edit distance in detecting anomalous phenomena. Our results suggest that in appropriate contexts, RH distance has advantages over more computationally intensive similarity measures.

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading over contact networks. Often, the networks over which these processes spread are dynamic in nature, and can be modelled with temporal graphs. Here, we study the problem of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally) reachable from a given starting point. This could be used to control the spread of a disease, rumour, etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process starting at any single vertex can be transferred to only a limited number of other vertices using a temporally-feasible path. We introduce a natural edge-deletion problem for temporal graphs and provide positive and negative results on its computational complexity and approximability. [ABSTRACT FROM AUTHOR]

Time-evolving or temporal graphs gain more and more popularity when exploring complex networks. In this context, the multistage view on computational problems is among the most natural frameworks. Roughly speaking, herein one studies the different (time) layers of a temporal graph (effectively meaning that the edge set may change over time, but the vertex set remains unchanged), and one searches for a solution of a given graph problem for each layer. The twist in the multistage setting is that the solutions found must not differ too much between subsequent layers. We relax on this already established notion by introducing a global instead of the local budget view studied so far. More specifically, we allow for few disruptive changes between subsequent layers but request that overall, that is, summing over all layers, the degree of change is moderate. Studying several classical graph problems (both NP-hard and polynomial-time solvable ones) from a parameterized complexity angle, we encounter both fixed-parameter tractability and parameterized hardness results. Surprisingly, we find that sometimes the global multistage versions of NP-hard problems such as Vertex Cover turn out to be computationally more tractable than the ones of polynomial-time solvable problems such as Matching. In addition to time complexity, we also analyze the space efficiency of our algorithms. [ABSTRACT FROM AUTHOR]

Property graphs are a common form of linked data, with path queries used to traverse and explore them for enterprise transactions and mining. Temporal property graphs are a recent variant where time is a first-class entity to be queried over, and their properties and structure vary over time. These are seen in social, telecom, transit and epidemic networks. However, current graph databases and query engines have limited support for temporal relations among graph entities, no support for time-varying entities and/or do not scale on distributed resources. We address this gap by extending a linear path query model over property graphs to include intuitive temporal predicates and aggregation operators over temporal graphs. We design a distributed execution model for these temporal path queries using the interval-centric computing model, and develop a novel cost model to select an efficient execution plan from several. We perform detailed experiments of our G r a n i t e distributed query engine using both static and dynamic temporal property graphs as large as 52 M vertices, 218 M edges and 325 M properties, and a 1600-query workload, derived from the LDBC benchmark. We frequently offer sub-second query latencies on a commodity cluster, which is 149 × – 1140 × faster compared to industry-leading Neo4J shared-memory graph database and the JanusGraph/Spark distributed graph query engine. G r a n i t e also completes 100% of the queries for all graphs, compared to only 32–92% workload completion by the baseline systems. Further, our cost model selects a query plan that is within 10% of the optimal execution time in 90% of the cases. Despite the irregular nature of graph processing, we exhibit a weak-scaling efficiency of ≥ 60 % on 8 nodes and ≥ 40 % on 16 nodes, for most query workloads. • Proposes a linear path query model over temporal property graphs. • Provides a distributed execution model which can scale to large graphs. • Includes a novel cost model to choose the optimum execution plan. • Evaluates our distributed engine for diverse query workloads over large property graphs on a commodity cluster. [ABSTRACT FROM AUTHOR]

Abstract A plethora of centrality measures or rankings have been proposed to account for the importance of the nodes of a network. In the seminal study of Boldi and Vigna (2014), the comparative evaluation of centrality measures was termed a difficult, arduous task. In networks with fast dynamics, such as the Twitter mention or retweet graphs, predicting emerging centrality is even more challenging. Our main result is a new, temporal walk based dynamic centrality measure that models temporal information propagation by considering the order of edge creation. Dynamic centrality measures have already started to emerge in publications; however, their empirical evaluation is limited. One of our main contributions is creating a quantitative experiment to assess temporal centrality metrics. In this experiment, our new measure outperforms graph snapshot based static and other recently proposed dynamic centrality measures in assigning the highest time-aware centrality to the actually relevant nodes of the network. Additional experiments over different data sets show that our method perform well for detecting concept drift in the process that generates the graphs.

We introduce the notions of blackout-tolerant temporal α -spanner of a temporal graph G which is a subgraph of G that preserves the distances between pairs of vertices of interest in G up to a multiplicative factor of α , even when the graph edges at a single time-instant become unavailable. In particular, we consider the single-source , single-pair , and all-pairs cases and, for each case we look at three quality requirements: exact distances (i.e., α = 1), almost-exact distances (i.e., α = 1 + ε for an arbitrarily small constant ε > 0), and connectivity (i.e., unbounded α). We provide almost tight bounds on the size of such spanners for general temporal graphs and for temporal cliques , showing that they are either very sparse (i.e., they have O ˜ (n) edges) or they must have size Ω (n 2) in the worst case, where n is the number of vertices of G. We also investigate multiple blackouts and k-edge fault-tolerant temporal spanners. [ABSTRACT FROM AUTHOR]

Dynamic networks are a complex subject. Not only do they inherit the complexity of static networks (as a particular case); they are also sensitive to definitional subtleties that are a frequent source of confusion and incomparability of results in the literature. In this paper, we take a step back and examine three such aspects in more details, exploring their impact in a systematic way; namely, whether the temporal paths are required to be strict (i.e., the times along a path must increasing, not just be non-decreasing), whether the time labeling is proper (two adjacent edges cannot be present at the same time) and whether the time labeling is simple (an edge can have only one presence time). In particular, we investigate how different combinations of these features impact the expressivity of the graph in terms of reachability. Our results imply a hierarchy of expressivity for the resulting settings, shedding light on the loss of generality that one is making when considering either combination. Some settings are more general than expected; in particular, proper temporal graphs turn out to be as expressive as general temporal graphs where non-strict paths are allowed. Also, we show that the simplest setting, that of happy temporal graphs (i.e., both proper and simple) remains expressive enough to emulate the reachability of general temporal graphs in a certain (restricted but useful) sense. Furthermore, this setting is advocated as a target of choice for proving negative results. We illustrate this by strengthening two known results to happy graphs (namely, the inexistence of sparse spanners, and the hardness of computing temporal components). Overall, we hope that this article can be seen as a guide for choosing between different settings of temporal graphs, while being aware of the way these choices affect generality. [ABSTRACT FROM AUTHOR]

The real-time nature and massive volume of social-media data has converted news portals and micro-blogging platforms into social sensors, causing a flourishing of research on story or event detection in online user-generated content and social-media text streams. Existing approaches to story identification broadly fall into two categories. Approaches in the first category extract stories as cohesive substructures in a graph representing the strength of association between terms. The latter category includes approaches that analyze the temporal evolution of individual terms and identify stories by grouping terms with similar anomalous temporal behavior. Both categories have their own limitations. Approaches in the first category are unable to distinguish ever-popular concepts from stories that buzz in a time interval of interest, i.e., attract an amount of attention that deviates significantly from the typical level observed. The second category ignores term co-associations and the wealth of information captured by them. In this work we advance the literature on story identification by profitably combining the peculiarities of the two main state-of-the-art approaches. We propose a novel method that characterizes abnormal association between terms in a certain time window and leverages the graph structure induced by such anomalous associations so as to identify stories as subsets of terms that are cohesively associated in this graph. Experiments performed on two datasets extracted from a real-world web-search query log and a news corpus, respectively, attest the superiority of the proposed method over the two main existing story-identification approaches. [ABSTRACT FROM AUTHOR]

An interval temporal network is, informally speaking, a network whose links change with time. The term interval means that a link may exist for one or more time intervals, called availability intervals of the link, after which it does not exist (until, maybe, a further moment in time when it starts being available again). In this model, we consider continuous time and high-speed (instantaneous) information dissemination. An interval temporal network is connected during a period of time [ x , y ] , if it is connected for all time instances t ∈ [ x , y ] (instantaneous connectivity). In this work, we study instantaneous connectivity issues of interval temporal networks. We provide a polynomial-time algorithm that answers if a given interval temporal network is connected during a time period. If the network is not connected throughout the given time period, then we also give a polynomial-time algorithm that returns large components of the network that remain connected and remain large during [ x , y ] ; the algorithm also considers the components of the network that start as large at time t = x but dis-connect into small components within the time interval [ x , y ] , and answers how long after time t = x these components stay connected and large. Finally, we examine a case of interval temporal networks on tree graphs where the lifetimes of links and, thus, the failures in the connectivity of the network are not controlled by us; however, we can "feed" the network with extra edges that may re-connect it into a tree when a failure happens, so that its connectivity is maintained during a time period. We show that we can with high probability maintain the connectivity of the network for a long time period by making these extra edges available for re-connection using a randomized approach. Our approach also saves some cost in the design of availabilities of the edges; here, the cost is the sum, over all extra edges, of the length of their availability-to-reconnect interval. [ABSTRACT FROM AUTHOR]

A temporal graph G is a pair (G , λ) where G is a graph and λ is a function on the edges of G describing when each edge is active. Temporal connectivity then concerns only paths that respect the flow of time. In this context, it is known that Menger's Theorem does not hold. In a seminal paper, Kempe, Kleinberg and Kumar (STOC'2000) defined a graph to be Mengerian if equality holds for every time-function. They then proved that, if each edge is allowed to be active only once in (G , λ) , then G is Mengerian if and only if G has no gem as topological minor. In this paper, we generalize their result by allowing edges to be active more than once, giving a characterization also in terms of forbidden structures. We additionally provide a polynomial time recognition algorithm. [ABSTRACT FROM AUTHOR]