Graph Analysis Using Fast Fourier Transform Applied on Grayscale Bitmap Images

Abstract

There is spiking interest in graph analysis, mainly sparked by social network analysis done for various purposes. With social network graphs often achieving very large size, there is a need for capable tools to perform such an analysis. In this article, we contribute to this area by presenting an original approach to calculating various graph morphisms, designed with overall performance and scalability as the primary concern. The proposed method generates a list of candidates for further analysis by first decomposing a complex network into a set of sub-graphs, transforming sub-graphs into intermediary structures, which are then used to generate grey-scaled bitmap images, and, eventually, performing image comparison using Fast Fourier Transform. The paper discusses the proof-of-concept implementation of the method and provides experimental results achieved on sub-graphs in different sizes randomly chosen from a reference dataset. Planned future developments and key considered areas of application are also described.

Keywords

• graphs
• social network analysis
• isomorphism
• big data
• image comparison