Efficient identifications of structural similarities for graphs

Zheng Fang () and Jie Wang ()
Additional contact information
Zheng Fang: University of Massachusetts
Jie Wang: University of Massachusetts

Journal of Combinatorial Optimization, 2014, vol. 27, issue 2, No 1, 209-220

Abstract: Abstract Measuring and detecting graph similarities is an important topic with numerous applications. Early algorithms often incur quadratic time or higher, making them unsuitable for graphs of very large scales. Motivated by the cooling process of an object in a thermodynamic system, we devise a new method for measuring graph similarities that can be carried out in linear time. Our algorithm, called Random Walker Termination (RWT), employs a large number of random walkers to capture the structure of a given graph using termination rates in a time sequence. To verify the effectiveness of the RWT algorithm, we use three major graph models, namely, the Erdős-Rényi random graphs, the Watts-Strogatz small-world graphs, and the Barabási-Albert preferential-attachment graphs, to generate graphs of different sizes. We show that the RWT algorithm performs well for graphs generated by these models. Our experiment results agree with the actual similarities of generated graphs. Using self-similarity tests, we show that RWT is sufficiently stable to generate consistent results. We use the graph edge rerouting test and the cross model test to demonstrate that RWT can effectively identify structural similarities between graphs.

Keywords: Graph similarity; Large-scale graphs; Linear-time algorithm (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9505-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jcomop:v:27:y:2014:i:2:d:10.1007_s10878-012-9505-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9505-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().