### The Right Way to Search Evolving Graphs

**2016-01-29**

1601.08189 | cs.SI

Evolving graphs arise in problems where interrelations between data change
over time. We present a breadth first search (BFS) algorithm for evolving
graphs that computes the most direct influences between nodes at two different
times. Using simple examples, we show that naive unfoldings of adjacency
matrices miscount the number of temporal paths. By mapping an evolving graph to
an adjacency matrix of an equivalent static graph, we prove that our
generalization of the BFS algorithm correctly accounts for paths that traverse
both space and time. Finally, we demonstrate how the BFS over evolving graphs
can be applied to mine citation networks.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2017-07-01**

1707.00143 | cs.LG

Approximate nearest neighbor search (ANNS) is a fundamental problem in
databases and data mining. A … show more

**2017-11-11**

1711.04150 | cs.SI

Analyzing the temporal behavior of nodes in time-varying graphs is useful for
many applications such… show more

**2019-05-13**

1905.05304 | cs.DM

We study the computational complexity of finding maximum-cardinality temporal
matchings in temporal … show more

**2019-03-08**

1903.03636 | cs.CC

Temporal graphs are used to abstractly model real-life networks that are
inherently dynamic in natur… show more

**2019-03-26**

1903.10699 | cs.LG

Most of real-world graphs are {\em dynamic}, i.e., they change over time.
However, while the regress… show more

**2019-01-05**

1901.01412 | cs.DS

We investigate the time-complexity of the All-Pairs Max-Flow problem: Given a
graph with $n$ nodes a… show more

**2019-03-27**

1903.11246 | cs.SY

This paper presents conditions for establishing topological controllability
in undirected networks o… show more

**2018-09-10**

1809.03457 | cs.SI

Recent advances in data collection and storage have allowed both researchers
and industry alike to c… show more

**2019-03-13**

1903.05377 | cs.DS

The neighbourhood matrix, $\mathcal{NM}(G)$, a novel representation of graphs
proposed in \cite {ALP… show more

**2017-09-15**

1709.05132 | math.NA

Identifying important components in a network is one of the major goals of
network analysis. Popular… show more

**2019-04-12**

1904.06449 | cs.LG

Networks evolve continuously over time with the addition, deletion, and
changing of links and nodes.… show more

**2019-03-21**

1903.08889 | cs.LG

In this work, we present a method for node embedding in temporal graphs. We
propose an algorithm tha… show more

**2018-09-14**

1809.05481 | cs.DS

We present algorithms for multi-modal route planning in road and public
transit networks, as well as… show more

**2018-10-01**

1810.00980 | cs.SI

Pattern counting in graphs is fundamental to network science tasks, and there
are many scalable meth… show more

**2018-10-08**

1810.03491 | cs.DS

We consider the problem of incremental cycle detection and topological
ordering in a directed graph … show more

**2019-01-16**

1901.05264 | cs.CC

Exact pattern matching in labeled graphs is the problem of searching paths of
a graph $G=(V,E)$ that… show more