Search

Dynamic (Temporal) graphs capture the valuable evolution of real-world systems, from the continuously evolving patterns of social interactions and genetic pathways to the dynamic fluctuations of economic forces. Detecting communities for such evolving networks poses unique challenges. Detecting and analyzing the evolution of communities within dynamic graphs unlocks valuable insights into the underlying structural and temporal patterns of real-world systems. However, the sheer volume of modern graph data and the inherent complexity of the temporal dimension pose significant challenges to scalable community detection algorithms. Addressing this gap, our work explores the limited landscape of scalable distributed-memory parallel methods specifically designed for dynamic network community detection. We propose a novel parallel algorithm, DyG-DPCD (Dynamic Graph Distributed Parallel Community Detection), to detect communities in dynamic networks using the Message Passing Interface (MPI) framework. We present a vertex-centric approach, allowing us to detect communities through local optimization. Furthermore, we enhance our baseline algorithm by incorporating three heuristics, which improve the algorithm’s performance significantly while maintaining the quality of the solutions. We demonstrate the efficiency of our algorithm by experimenting on several real-world large-scale networks with hundreds of millions of edges spanning diverse domains. Notably, DyG-DPCD achieves speedups between 25 × and 30 × for large networks that we experimented on using NERSC compute nodes. Our algorithm outperforms the STINGER parallel re-agglomeration algorithm by 30 × . [ABSTRACT FROM AUTHOR]

Given a directed temporal graph, a start node s$$ s $$, and p$$ p $$ objectives, the task in the single‐source multiobjective temporal shortest path problem (SSMTSPP) consists of computing the set of nondominated images of temporal s$$ s $$‐v$$ v $$‐paths for each node v≠s$$ v\ne s $$ as well as one corresponding efficient path for each of these images. This problem generalizes both the multiobjective shortest path problem in static graphs and the single‐objective temporal shortest path problem. In this article, we provide a general label setting algorithm for the SSMTSPP that can handle a large variety of different objectives. The only condition imposed on the objectives is a monotonicity property that generalizes the nonnegativity of the arc costs required for the well‐known label setting algorithm for solving the static single‐source shortest path problem in both the single objective and the multiobjective case. Our analysis of the presented algorithm shows that its worst‐case running time is polynomial in the sum of the input size of the problem instance and the number of nondominated images, which implies that it runs in polynomial time as long as the number of nondominated images is polynomial in the instance size (i.e., for all tractable versions of the problem). To complement this result, we provide a complete classification into tractable and intractable problems for all SSMTSPPs involving a large variety of objectives. In particular, using our general analysis, this provides a large range of specific SSMTSPPs for which our general label setting algorithm runs in polynomial time. [ABSTRACT FROM AUTHOR]

In the last decades, urbanization and population growth substantially increased water consumption for agricultural, industrial, and residential purposes. Characterizing the interplay between environmental variables and water resources plays a critical role in establishing effective water management policies. In this paper, we apply Canonical Correlation Analysis (CCA) in a set of climate and hydrological indicators to investigate the behavior of these environmental variables over time in different geographical regions of California, as well as the relationship among these regions. CCA served as a base to establish a temporal graph that models the relationship between the stations over time, and advanced graph visualization techniques are used to produce patterns that aid in the comprehension of the underlying phenomena. Our results identified important temporal patterns, such as heterogeneous behavior in the dry season and lower correlation between the stations in La Niña years. We show that the combination of CCA and visual analytics can assist water experts in identifying important climate and hydrological events in different scenarios. [ABSTRACT FROM AUTHOR]

Temporal graphs represent graph evolution over time, and have been receiving considerable research attention. Work on expressing temporal graph patterns or discovering temporal motifs typically assumes relatively simple temporal constraints, such as journeys or, more generally, existential constraints, possibly with finite delays. In this paper we propose to use timed automata to express temporal constraints, leading to a general and powerful notion of temporal basic graph pattern (BGP). The new difficulty is the evaluation of the temporal constraint on a large set of matchings. An important benefit of timed automata is that they support an iterative state assignment, which can be useful for early detection of matches and pruning of non-matches. We introduce algorithms to retrieve all instances of a temporal BGP match in a graph, and present results of an extensive experimental evaluation, demonstrating interesting performance trade-offs. We show that an on-demand algorithm that processes total matchings incrementally over time is preferable when dealing with cyclic patterns on sparse graphs. On acyclic patterns or dense graphs, and when connectivity of partial matchings can be guaranteed, the best performance is achieved by maintaining partial matchings over time and allowing automaton evaluation to be fully incremental. The code and datasets used in our analysis are available at http://github.com/amirpouya/TABGP. [ABSTRACT FROM AUTHOR]

Consider a directed temporal graph G = (V , E) with time ranges on the edges. There can be more than one range on an edge, and each range carries a positive traversal time. Let n = | V | and let Δ be the total number of time ranges in G. We assume that Δ = Ω (n). We study the problem of computing shortest journeys that start from a fixed source vertex s within a given time interval [ t b , t e) , where the cost of a journey is equal to the sum of traversal times of the edges on it at the times of crossing those edges. We can construct in O (Δ 2 log Δ) time a data structure of size O (n Δ) such that for any vertex v and any time t , we can report in O (log Δ) time the cost of the shortest journey that starts from s within [ t b , t e) and arrives at v no later than t. The journey achieving the reported cost can be produced in time linear in its complexity. [ABSTRACT FROM AUTHOR]

Interactions among entities are usually modeled using graphs. In many real scenarios, these relations may change over time, and different kinds exist among entities that need to be integrated. We introduce a new network model called temporal dual network, to deal with interactions which change over time and to integrate information coming from two different networks. In this new model, we consider a fundamental problem in graph mining, that is, finding the densest subgraphs. To deal with this problem, we propose an approach that, given two temporal graphs, (1) produces a dual temporal graph via alignment and (2) asks for identifying the densest subgraphs in this resulting graph. For this latter problem, we present a polynomial-time dynamic programming algorithm and a faster heuristic based on constraining the dynamic programming to consider only bounded temporal graphs and a local search procedure. We show that our method can output solutions not far from the optimal ones, even for temporal graphs having 10000 vertices and 10000 timestamps. Finally, we present a case study on a real dual temporal network. [ABSTRACT FROM AUTHOR]

We study the NP-hard Temporal (s , z) -Separation problem on temporal graphs, which are graphs with fixed vertex sets but edge sets that change over discrete time steps. We tackle Temporal (s , z) -Separation by restricting the layers (i.e., graphs characterized by edges that are present at a certain point in time) to specific graph classes. We restrict the layers of the temporal graphs to be either all split graphs or all permutation graphs (both being perfect graph classes) and provide both intractability and tractability results. In particular, we show that in general Temporal (s , z) -Separation remains NP-hard both on temporal split and temporal permutation graphs, but we also spot promising islands of fixed-parameter tractability particularly based on parameterizations that measure the amount of "change over time". [ABSTRACT FROM AUTHOR]

We study the fixed-parameter tractability of the problem of deciding whether a given temporal graph admits a temporal walk that visits all vertices (temporal exploration) or, in some variants, a certain subset of the vertices. In the strict variant, edges must be traversed in strictly increasing timesteps; in the non-strict variant, any number of edges can be traversed in each timestep. For both variants, we give FPT algorithms for finding a temporal walk that visits a given set X of vertices, parameterised by | X | , and for finding a temporal walk that visits at least k distinct vertices, parameterised by k. We also show W [ 2 ] -hardness for a set version of temporal exploration. For the non-strict variant, we give an FPT algorithm for temporal exploration parameterised by the lifetime, and show that temporal exploration can be solved in polynomial time if the graph in each timestep has at most two connected components. [ABSTRACT FROM AUTHOR]

The business owners have significantly focused on improving the business to business (B2B) services to enhance business productivity. Numerous methods have already been proposed for the personalized end users recommendation systems, but there are no such attempts for business owners. The business customers buying processes consists of various marketing campaign requirements to promote their services or products effectively. It requires an intelligent B2B marketing campaigns recommendation system to meet the business goals for business customers. The B2B marketing campaigns recommendations are required to increase the business earning, but complex items and user profiles lead to challenging research problems. To end this, we propose a novel framework for intelligent B2B marketing campaign recommendations using the fuzzy preference (FP) personalized temporal graph (PTG) and low-rank graph reconstruction (LRGR). The proposed model FP-PTG-LRGR consists of three steps such as pre-processing, hybrid preference extractions, and recommendations. We first designed pre-processing algorithm using natural language processing (NLP) to remove the noisy data. The pre-processing is required to enhance the reliability and accuracy of recommendations. After that, we proposed the hybrid behavior analysis technique called FP-PTG model for extracting the business customer's preferences. FP-PTG aims to represent the buying process information of every business customer accurately. The FP technique is integrated with PTG to overcome the crip/vague preferences that form the FP-PTG model. The B2B marketing campaign order preferences for personalized businesses have effectively represented and merged using FP-PTG. Finally, we applied LRGR to estimate the intelligent B2B marketing campaign recommendations for individual business customers by discovering the unobserved edges in FP-PTG. We have performed experimental studies using publically available B2B marketing datasets, and outcomes claim that FP-PTG-LRGR outperformed existing methods for B2B marketing campaign recommendations. Experimental results of FP-PTG-LRGR show the improvement of precision rate by 11.5%, recall rate by 11.23%, and accuracy by 12.11%. [ABSTRACT FROM AUTHOR]

Addressing a quest by Gupta et al. (in: Proceedings of the 41st international colloquium on automata, languages, and programming (ICALP 2014), vol 8572 of LNCS. Springer, pp 563–575, 2014), we provide a first, comprehensive study of finding a short s–t path in the multistage graph model, referred to as the Multistages–tPath problem. Herein, given a sequence of graphs over the same vertex set but changing edge sets, the task is to find short s–t paths in each graph ("snapshot") such that in the found path sequence the consecutive s–t paths are "similar". We measure similarity by the size of the symmetric difference of either the vertex set (vertex-similarity) or the edge set (edge-similarity) of any two consecutive paths. We prove that these two variants of Multistages–tPath are already NP -hard for an input sequence of only two snapshots and maximum vertex degree four. Motivated by this fact and natural applications of this scenario e.g. in traffic route planning, we perform a parameterized complexity analysis. Among other results, for both variants, vertex- and edge-similarity, we prove parameterized hardness (W[1] -hardness) regarding the parameter path length (solution size). As a further conceptual investigation, we then modify the multistage model by asking for dissimilar consecutive paths. As one of the main technical results (employing so-called representative sets known from non-temporal settings), we prove that dissimilarity allows for fixed-parameter tractability for the parameter solution size, contrasting with our W[1]-hardness proof of the corresponding similarity case. We also provide partially positive results concerning efficient and effective data reduction (kernelization). [ABSTRACT FROM AUTHOR]

Change-point detection in dynamic networks is a challenging task which is particularly due to the complex nature of temporal graphs. Existing approaches are based on the extraction of a network's information by the reduction to a model or to a single metric. Whereas the former one requires restrictive assumptions and has limited applicability for real-world social networks, the latter one may suffer from a huge information loss. We demonstrate that an extension to a well-balanced multivariate approach that uses multiple metrics jointly to cover the relevant network information can overcome both issues, since it is applicable to arbitrary network shapes and promises to strongly mitigate the information loss. In this context, we give guidelines on the crucial questions of how to properly choose a suitable multivariate metric set together with the choice of a meaningful parametric or nonparametric control chart and show that an improper application may easily lead to unsatisfying results. Furthermore, we identify a solution that achieves reasonable performances in flexible circumstances in order to give a reliably applicable approach for various types of social networks and application fields. Our findings are supported by the use of extensive simulation studies, and its applicability is demonstrated on two real-world data sets from economics and social sciences. [ABSTRACT FROM AUTHOR]

We introduce a natural temporal analogue of Eulerian circuits and prove that, in contrast to the static case, it is NP -hard to determine whether a given temporal graph is temporally Eulerian even if strong restrictions are placed on the structure of the underlying graph and each edge is active at only three times. However, we do obtain an FPT -algorithm with respect to a new parameter called interval-membership-width which restricts the times assigned to different edges; we believe that this parameter will be of independent interest for other temporal graph problems. Our techniques also allow us to resolve two open questions of Akrida, Mertzios and Spirakis [CIAC 2019] concerning a related problem of exploring temporal stars. [ABSTRACT FROM AUTHOR]

An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graph G at least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. But what if Euler had to take a bus? In a temporal graph (G , λ) , with λ : E (G) → 2 [ τ ] , an edge e ∈ E (G) is available only at the times specified by λ (e) ⊆ [ τ ] , in the same way the connections of the public transportation network of a city or of sightseeing tours are available only at scheduled times. In this paper, we deal with temporal walks, local trails, and trails, respectively referring to edge traversal with no constraints, constrained to not repeating the same edge in a single timestamp, and constrained to never repeating the same edge throughout the entire traversal. We show that, if the edges are always available, then deciding whether (G , λ) has a temporal walk or trail is polynomial, while deciding whether it has a local trail is NP -complete even if τ = 2 . In contrast, in the general case, solving any of these problems is NP -complete, even under very strict hypotheses. We finally give XP algorithms parametrized by τ for walks, and by τ + t w (G) for trails and local trails, where t w (G) refers to the treewidth of G . [ABSTRACT FROM AUTHOR]