Network embedding (NE) aims to learn low dimensional node representations, wherein both neural-based (NNE) and factorization-based (FNE) methods commonly employ negative sampling (NS) as an essential component. However, the role of NS differs markedly between these two paradigms: in NNE, negative samples are randomly chosen to facilitate efficient training, while in FNE, the distribution of negative samples plays a pivotal role in deriving the factorized matrix. In this work, we propose LocAPS (Loccal cluster-based Adaptive Positive Sampling), a novel sampling strategy that adaptively determines positive samples for each node based on local clustering. Building on LocAPS, we develop an enhanced NNE method, VERSE+, which achieves both sampling and training in linear time. For FNE, we introduce an adaptive negative sampling distribution derived from LocAPS, which tailors the sampling probability for each node. This distribution informs the construction of a factorized matrix that adaptively retains information from the similarity matrix. Moreover, its node-wise nature enables the development of FREDE+, an efficient streaming-style NE method with linear time and space complexity. We conduct extensive experiments on multiple real-world datasets, evaluating our methods on node classification and link prediction tasks, demonstrating their effectiveness and superior performance.

Label-constrained reachability (LCR) has been ex-tensively studied. However, these studies have neglected two aspects: the label sequence and time-dependent properties. When processing reachability queries, not only label presence but also label sequence and time-dependent properties should be considered. Various real-world scenarios, including vehicular networks, computing networks, and biological networks, require such queries. In this paper, we present a formal definition of time-dependent label-constrained reachability (TDLCR) queries based on LCR. These queries require both label sequence and time-dependent constraints to be considered, thus introducing a higher level of complexity. To address this challenge, we propose two indexing algorithms that are optimized for the label constraint: OneL and TD2H. OneL builds a single-label index for each vertex and provides a baseline for solving the TDLCR problem. TD2H is based on classical 2-hop index with excellent query efficiency, while innovative pruning rules and vertex order strategies are proposed to reduce indexing overhead. To further balance indexing overhead and query efficiency and to optimize the time-dependent constraint, we introduce a BII algorithm. It effectively improves index construction efficiency by building only a local index instead of a global one. Finally, experiments on many real datasets demonstrate that although the BII has a slightly inferior query time to TD2H, it has a significant advantage in the index construction.

The influence maximization in a social network has been extensively studied, however, existing works have neglected the fact that time-dependent reachable information plays an important role in this query processing. Many real-world applications, such as location-based recommendations, location-based advertisements, and location-based emergency message distribution, require such a query. In this paper, we formally define reachability-driven influence maximization (RDIM) in time-dependent road-social networks, to find a seed set that maximizes the expected influence over potential users, i.e., target users, who are likely to reach a given location within a deadline. To efficiently compute the influence diffusion, we define a versatile influence (VI) diffusion model based on user relationships and time-dependent location information. The RDIM has two critical challenges: identifying the target users and finding the seed nodes. We propose a TS-index with temporal and regional dimensions for identifying the target users by employing a reachable region. To find seed nodes, we construct a CTS-index by extending a community dimension into the TS-index to enhance the calculation of social influence by using the relationship between communities and the reachable region. Finally, we use the real road and social network data to empirically verify the efficiency and effectiveness of our solutions.

Multimodal path queries over transportation networks are receiving increasing attention due to their widespread applications. A multimodal path query consists of finding multimodal journeys from source to destination in transportation networks, including unrestricted walking, driving, cycling, and schedule-based public transportation. Transportation networks are generally continent-sized. This characteristic highlights the need for parallel computing to accelerate multimodal path queries. Meanwhile, transportation networks are often fragmented and distributively stored on different machines. This situation calls for exploiting parallel computing power for these distributed systems. Therefore, in this paper, we studydistributed multimodal path (DMP) queriesover large transportation networks. We develop algorithms to explore parallel computation. When evaluating a DMP query$Q$on a distributed multimodal graph$Gmult$, we show that the algorithms possess the following performance guarantees, irrespective of how$Gmult$is fragmented and distributed: (1) each machine is visited only once; (2) the total network traffic is determined by the size of$Q$and the fragmentation of$Gmult$; (3) the response time is decided by the largest fragment of$Gmult$; and (4) the algorithm is parallel scalable. Using real-life and synthetic data, we experimentally verify that the algorithms are scalable on large graphs.

Constrained route planning (CRP) on transportation networks has been extensively studied because of its broad applications, such as route recommendation. However, the existing works on CRP neglect the time-dependent and multi-modal properties of transportation networks. This paper proposes an approach for CRP over multi-modal time-dependent networks. Specifically, we design two novel constrained route planning algorithms, function-dependent routing and labeling-index-based routing. While function-dependent routing generates an accurate route to CRP by traversing the network, labeling-index-based one ensures the fast response with the support of an efficient index and the compression scheme of networks. In order to demonstrate the efficiency and effectiveness of our proposed algorithms, experiments are performed over real datasets.

Weight-constrained route planning (WRP) over static graphs has been extensively studied due to its wide application to transportation networks. However, real transportation networks often evolve over time and are thus modeled as time-dependent graphs. In this paper, we study the WRP problem over a large time-dependent graph by incorporating continuous time and weight functions into it. Most existing works regarding route planning over time-dependent graphs are based on the first-in-first-out (FIFO) property. Unfortunately, the FIFO property does not hold for our problem. To solve the problem, we propose two novel route planning algorithms, namely, a baseline algorithm and an advanced algorithm. Specifically, the advanced algorithm is even more efficient than the baseline algorithm, as the advanced algorithm incorporates a fast traversal scheme and tight bounds of time functions to terminate the traversal as early as possible. We confirm the effectiveness and efficiency of our algorithms by extensive experiments on real datasets.

Abstract A time-dependent graph is, informally speaking, a graph structure dynamically changes with time. In such graphs, the weights associated with edges dynamically change over time, that is, the edges in such graphs are activated by sequences of time-dependent elements. Many real-life scenarios can be better modeled by time-dependent graphs, such as bioinformatics networks, transportation networks, and social networks. In particular, the time-dependent graph is a very broad concept, which is reflected in the related research with many names, including temporal graphs, evolving graphs, time-varying graphs, historical graphs, and so on. Though static graphs have been extensively studied, for their time-dependent generalizations, we are still far from a complete and mature theory of models and algorithms. In this paper, we discuss the definition and topological structure of time-dependent graphs, as well as models for their relationship to dynamic systems. In addition, we review some classic problems on time-dependent graphs, e.g., route planning, social analysis, and subgraph problem (including matching and mining). We also introduce existing time-dependent systems and summarize their advantages and limitations. We try to keep the descriptions consistent as much as possible and we hope the survey can help practitioners to understand existing time-dependent techniques.

The constrained shortest path (CSP) query over static graphs has been extensively studied, since it has wide applications in transportation networks, telecommunication networks and etc. Such networks are dynamic and evolve over time, being modeled as time-dependent graphs. Therefore, in this paper, we study the CSP query over a large time-dependent graph. Specifically, we study the point CSP (PCSP) query and interval CSP (ICSP) query. We formally prove that it is NP-complete to process a PCSP query and at least EXPSPACE to answer an ICSP query. We propose approximate sequential algorithms to answer the PCSP and ICSP queries efficiently. We also develop parallel algorithms for the queries that guarantee to scale with big time-dependent graphs. Using real-life graphs, we experimentally verify the efficiency and scalability of our algorithms.