Subgraphs as a Measure of Similarity

Josef Lauri ()
Additional contact information
Josef Lauri: University of Malta, Department of Mathematics

Chapter Chapter 12 in Structural Analysis of Complex Networks, 2011, pp 319-334 from Springer

Abstract: Abstract How similar can two graphs be? The ultimate positive answer to this question is, of course, when the two graphs are isomorphic. However, how much internal structure can two nonisomorphic graphs share? We show what the answer can look like if the measure of similarity between the two graphs is taken to be the number of isomorphic subgraphs which they share. We see how this notion is related to the internal symmetries of a graph and that therefore, for most graphs, their internal structure forces them to be very dissimilar to other graphs. We also indicate some attempts to find nonisomorphic graphs which are very similar in terms of the common subgraphs which they share. We also point out some issues of computational complexity and some possible applications associated with this measure of graph similarity.

Keywords: Graph similarity; Isomorphic subgraphs; Graph reconstruction; Reconstruction numbers (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:sprchp:978-0-8176-4789-6_12

Ordering information: This item can be ordered from
http://www.springer.com/9780817647896

DOI: 10.1007/978-0-8176-4789-6_12

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().