Volume 7, Issue 2, April 2014, Pages 305 - 311
Approximate cycles count in undirected graphs
Authors
Maytham Safar, Khaled Mahdi, Hisham Farahat, Saud Albehairy, Ali Kassem, Khalid Alenzi
Corresponding Author
Maytham Safar
Received 13 February 2012, Accepted 14 February 2012, Available Online 1 April 2014.
- DOI
- 10.1080/18756891.2013.857893How to use a DOI?
- Keywords
- Complex networks, social networks, cyclic entropy, cycles
- 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.
- Copyright
- © 2017, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - JOUR AU - Maytham Safar AU - Khaled Mahdi AU - Hisham Farahat AU - Saud Albehairy AU - Ali Kassem AU - Khalid Alenzi PY - 2014 DA - 2014/04/01 TI - Approximate cycles count in undirected graphs JO - International Journal of Computational Intelligence Systems SP - 305 EP - 311 VL - 7 IS - 2 SN - 1875-6883 UR - https://doi.org/10.1080/18756891.2013.857893 DO - 10.1080/18756891.2013.857893 ID - Safar2014 ER -