Approximate cycles count in undirected graphs

Abstract

In social networks, counting the number of different cycle sizes can be used to measure the entropy of the network that represents its robustness. The exact algorithms to compute cycles in a graph can generate exact results but they are not guaranteed to run in a polynomial time. We present an approximation algorithm for counting the number of cycles in an undirected graph. The algorithm is regression-based and guaranteed to run in a polynomial time. A set of experiments are conducted to compare the results of our approximate algorithm with the results of an exact algorithm based on the Donald-Johnson backtracking algorithm.

Keywords:

• Complex networks
• social networks
• cyclic entropy
• cycles