Graph signatures: Identification and optimization

Balabhaskar Balasundaram, Juan S. Borrero and Hao Pan

European Journal of Operational Research, 2022, vol. 296, issue 3, 764-775

Abstract: 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 consecutive 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.

Keywords: Networks; Relational; Temporal; Cross-graph mining; Frequent subgraph mining (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721002770
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:296:y:2022:i:3:p:764-775

DOI: 10.1016/j.ejor.2021.03.051

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().