.png){kind=icon}
Return
Graph signatures: Identification and optimization
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2021.03.051.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We introduce a new graph-theoretic paradigm called a graph signature that describes persistent patterns in a sequence of graphs. This framework is motivated by the need to detect subgraphs of significance in temporal networks, e.g., social and biological networks that evolve over time. Because the subgraphs of interest may not all look alike in the snapshots of the temporal network, the framework deems a subgraph to be persistent if it satisfies one of several preselected properties in each snapshot of a con-secutive subsequence. The persistency requirement is parameterized by the length of this subsequence. This discrete mathematical framework can be viewed more broadly as a way to generalize classical graph properties and invariants associated with a single graph to a sequence of graphs. In this introductory article, we formulate the graph signature identification problem as a mixed-integer program and propose an algorithmic framework based on dynamic programming. This methodology is applicable to any collection of mixed-integer representable graph properties. We also demonstrate how this framework can be tailored to exploit property-specific decomposition and scale reduction techniques through three different computational case-studies. Our experiments show that the dynamic program-ming algorithm solves this problem across most instances in our test bed to optimality. Moreover, for the instances in our test bed, the optimal signature sizes are comparable to those of their static counterparts, suggesting that our new framework can identify subgraphs of significance in complex dynamic networks. (c) 2021 Elsevier B.V. All rights reserved.
Keywords:
Networks
Relational
Temporal
Cross-graph mining
Frequent subgraph mining
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
Cited Papers
.png){kind=icon}
ShareSave
View more