Clones in graphs

DOI10.1007/978-3-030-01851-1_6MaRDI QIDQ6165758zbMATH OpenFDO

Authors Stephan Doerfel, Tom Hanika, Gerd Stumme

Publication date 2 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.07849

zbMATH Keywords

clonesformal concept analysissocial network analysis

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Knowledge representation (68T30)

Abstract: Finding structural similarities in graph data, like social networks, is a far-ranging task in data mining and knowledge discovery. A (conceptually) simple reduction would be to compute the automorphism group of a graph. However, this approach is ineffective in data mining since real world data does not exhibit enough structural regularity. Here we step in with a novel approach based on mappings that preserve the maximal cliques. For this we exploit the well known correspondence between bipartite graphs and the data structure formal context $(G,M,I)$ from Formal Concept Analysis. From there we utilize the notion of clone items. The investigation of these is still an open problem to which we add new insights with this work. Furthermore, we produce a substantial experimental investigation of real world data. We conclude with demonstrating the generalization of clone items to permutations.

Recommendations

• Mining Graph Data
• scientific article; zbMATH DE number 3907592
• Subgraphs as a measure of similarity
• Graph-based mining of complex data
• Graph abstraction for closed pattern mining in attributed networks

Cited in

(1)

• Ordinal motifs in lattices

This page was built for publication: Clones in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165758)