Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDrawing Dynamic Graphs Without Timeslices
94
0
0.0
(
0
)
Added by
Daniel Archambault
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Timeslices are often used to draw and visualize dynamic graphs. While timeslices are a natural way to think about dynamic graphs, they are routinely imposed on continuous data. Often, it is unclear how many timeslices to select: too few timeslices can miss temporal features such as causality or even graph structure while too many timeslices slows the drawing computation. We present a model for dynamic graphs which is not based on timeslices, and a dynamic graph drawing algorithm, DynNoSlice, to draw graphs in this model. In our evaluation, we demonstrate the advantages of this approach over timeslicing on continuous data sets.
rate research
Read More
We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph $G$, the goal is to construct a straight-line drawing $Gamma$ of $G$ in the plane such that, for any two vertices $u$ and $v$ of $G$, the ratio between the minimum length of any path from $u$ to $v$ and the Euclidean distance between $u$ and $v$ is small. The maximum such ratio, over all pairs of vertices of $G$, is the spanning ratio of $Gamma$. First, we show that deciding whether a graph admits a straight-line drawing with spanning ratio $1$, a proper straight-line drawing with spanning ratio $1$, and a planar straight-line drawing with spanning ratio $1$ are NP-complete, $exists mathbb R$-complete, and linear-time solvable problems, respectively, where a drawing is proper if no two vertices overlap and no edge overlaps a vertex. Second, we show that moving from spanning ratio $1$ to spanning ratio $1+epsilon$ allows us to draw every graph. Namely, we prove that, for every $epsilon>0$, every (planar) graph admits a proper (resp. planar) straight-line drawing with spanning ratio smaller than $1+epsilon$. Third, our drawings with spanning ratio smaller than $1+epsilon$ have large edge-length ratio, that is, the ratio between the length of the longest edge and the length of the shortest edge is exponential. We show that this is sometimes unavoidable. More generally, we identify having bounded toughness as the criterion that distinguishes graphs that admit straight-line drawings with constant spanning ratio and polynomial edge-length ratio from graphs that require exponential edge-length ratio in any straight-line drawing with constant spanning ratio.
This paper proposes a novel model for predicting subgraphs in dynamic graphs, an extension of traditional link prediction. This proposed end-to-end model learns a mapping from the subgraph structures in the current snapshot to the subgraph structures in the next snapshot directly, i.e., edge existence among multiple nodes in the subgraph. A new mechanism named cross-attention with a twin-tower module is designed to integrate node attribute information and topology information collaboratively for learning subgraph evolution. We compare our model with several state-of-the-art methods for subgraph prediction and subgraph pattern prediction in multiple real-world homogeneous and heterogeneous dynamic graphs, respectively. Experimental results demonstrate that our model outperforms other models in these two tasks, with a gain increase from 5.02% to 10.88%.
Dynamic graph representation learning is a task to learn node embeddings over dynamic networks, and has many important applications, including knowledge graphs, citation networks to social networks. Graphs of this type are usually large-scale but only a small subset of vertices are related in downstream tasks. Current methods are too expensive to this setting as the complexity is at best linear-dependent on both the number of nodes and edges. In this paper, we propose a new method, namely Dynamic Personalized PageRank Embedding (textsc{DynamicPPE}) for learning a target subset of node representations over large-scale dynamic networks. Based on recent advances in local node embedding and a novel computation of dynamic personalized PageRank vector (PPV), textsc{DynamicPPE} has two key ingredients: 1) the per-PPV complexity is $mathcal{O}(m bar{d} / epsilon)$ where $m,bar{d}$, and $epsilon$ are the number of edges received, average degree, global precision error respectively. Thus, the per-edge event update of a single node is only dependent on $bar{d}$ in average; and 2) by using these high quality PPVs and hash kernels, the learned embeddings have properties of both locality and global consistency. These two make it possible to capture the evolution of graph structure effectively. Experimental results demonstrate both the effectiveness and efficiency of the proposed method over large-scale dynamic networks. We apply textsc{DynamicPPE} to capture the embedding change of Chinese cities in the Wikipedia graph during this ongoing COVID-19 pandemic (https://en.wikipedia.org/wiki/COVID-19_pandemic). Our results show that these representations successfully encode the dynamics of the Wikipedia graph.
This note wants to explain how to obtain meaningful pictures of (possibly high-dimensional) convex polytopes, triangulated manifolds, and other objects from the realm of geometric combinatorics such as tight spans of finite metric spaces and tropical polytopes. In all our cases we arrive at specific, geometrically motivated, graph drawing problems. The methods displayed are implemented in the software system polymake.
Let $Vsubsetmathbb{R}^2$ be a set of $n$ sites in the plane. The unit disk graph $DG(V)$ of $V$ is the graph with vertex set $V$ in which two sites $v$ and $w$ are adjacent if and only if their Euclidean distance is at most $1$. We develop a compact routing scheme for $DG(V)$. The routing scheme preprocesses $DG(V)$ by assigning a label $l(v)$ to every site $v$ in $V$. After that, for any two sites $s$ and $t$, the scheme must be able to route a packet from $s$ to $t$ as follows: given the label of a current vertex $r$ (initially, $r=s$) and the label of the target vertex $t$, the scheme determines a neighbor $r$ of $r$. Then, the packet is forwarded to $r$, and the process continues until the packet reaches its desired target $t$. The resulting path between the source $s$ and the target $t$ is called the routing path of $s$ and $t$. The stretch of the routing scheme is the maximum ratio of the total Euclidean length of the routing path and of the shortest path in $DG(V)$, between any two sites $s, t in V$. We show that for any given $varepsilon>0$, we can construct a routing scheme for $DG(V)$ with diameter $D$ that achieves stretch $1+varepsilon$ and label size $O(log Dlog^3n/loglog n)$ (the constant in the $O$-Notation depends on $varepsilon$). In the past, several routing schemes for unit disk graphs have been proposed. Our scheme is the first one to achieve poly-logarithmic label size and arbitrarily small stretch without storing any additional information in the packet.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
