The week's pick
Random Articles
Reseach Article
Performance Testing of RNSC and MCL Algorithms on Random Geometric Graphs
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 53 - Number 12 |
| Year of Publication: 2012 |
| Authors: Mousumi Dhara, K. K. Shukla |
10.5120/8471-2397
|
Mousumi Dhara, K. K. Shukla . Performance Testing of RNSC and MCL Algorithms on Random Geometric Graphs. International Journal of Computer Applications. 53, 12 ( September 2012), 5-11. DOI=10.5120/8471-2397
Abstract
The exploration of quality clusters in complex networks is an important issue in many disciplines, which still remains a challenging task. Many graph clustering algorithms came into the field in the recent past but they were not giving satisfactory performance on the basis of robustness, optimality, etc. So, it is most difficult task to decide which one is giving more beneficial clustering results compared to others in case of real–world problems. In this paper, performance of RNSC (Restricted Neighbourhood Search Clustering) and MCL (Markov Clustering) algorithms are evaluated on a random geometric graph (RGG). RNSC uses stochastic local search method for clustering of a graph. RNSC algorithm tries to achieve optimal cost clustering by assigning some cost functions to the set of clusterings of a graph. Another standard clustering algorithm MCL is based on stochastic flow simulation model. RGG has conventionally been associated with areas such as statistical physics and hypothesis testing but have achieved new relevance with the advent of wireless ad-hoc and sensor networks. In this study, the performance testing of these methods is conducted on the basis of cost of clustering, cluster size, modularity index of clustering results and normalized mutual information (NMI) using both real and synthetic RGG.
References
- Newman, M. E. J. 2001. Clustering and preferential attachment in growing networks. PhysicalReview E, 64:025102.
- Watts,Duncan J. and Strogatz,Steven H. 1998. Collective dynamics of 'small-world' networks. Nature, 393:440–442.
- Huberman,Bernardo A. 1999. Growth dynamics of the World-Wide Web. Nature, 401:131.
- Amaral,L. A. N. , Scala,A. , Barth´el´emy,M. , and Stanley,H. E. 2000. Classes of small-world networks. Proc. Natl. Acad. Sci. USA, 97:11149–11152.
- Penrose,M. 2003. Random Geometric Graphs (Oxford University Press, New York).
- Franceschetti,M. and Meester,R. 2007. Random Networks for Communication (Cambridge University Press, Cambridge, England).
- Kyrylyuk,V. , Hermant,M. C. , Schilling,T. , Klumperman,B. , Koning,C. E. , and Schoot,P. van der 2011. Controlling electrical percolation in multicomponent carbon nanotube dispersions, Nature Nanotech. 6, 364-369.
- Miller,J. C. , Soc. Roy, J. 2009. Spread of infectious disease through clustered populations, Interf. 6, 1121 -1134.
- Danon,L. , Ford,A. P. , House,T. , Jewell,C. P. , Keeling,M. J. , Roberts,G. O. , Ross,J. V. , and Vernon,M. C. 2011. Networks and the Epidemiology of Infectious Disease, Interdisc. Persp. Infect. Diseases, 284-909.
- Pueyo,S. , Grac¸a, P. M. L. D. A. , Barbosa,R. I. , Cots,R. , Cardona,E. , and Fearnside,P. M. 2010. Impact of boundaries on fully connected random geometric networks, Ecol. Lett. 13, 793.
- Palla,G. , Barab´asi,A. -L, and Vicsek,T. 2007. Quantifying social group evolution, Nature (London) 446, 664-667.
- Parshani,R. , Buldyrev,S. , andHavlin, S. 2011. Critical effect of dependency groups on the function of networks, Proc. Natl. Acad. Sci. 108, 1007.
- Haenggi,M. , Andrews,J. G. , Baccelli,F. , Dousse,O. , and Franceschetti,M. 2009. Stochastic geometry and random graphs for the analysis and design of wireless networks, IEEE J. Select. Area. Commun. 27, 1029-1046.
- Li,J. , Andrew,L. L. H. , Foh,Zukerman,C. H. , M. , and Chen,H. -H. 2009. Connectivity, Coverage and Placement in Wireless Sensor Networks,Sensors, vol. 9, no. 10, pp. 7664-7693.
- Wang,P. , Gonzalez,MC,Hidalgo, CA, Barabasi,A. -L2009. Understanding the spreading patterns of mobile phone viruses, Science 324, 1071-1076.
- Donath,W. E. and Hoffman,A. J. 1973. Lower Bounds for the Partitioning of Graphs, IBM J. Research and Development, vol. 17, pp. 422- 425.
- Hall, K. M. 1970. An R-Dimensional Quadratic Placement Algorithm, Management Science, vol. 11, no. 3, pp. 219-229.
- Ng,A. Y. , Jordan,M. , and Weiss,Y. 2001. On Spectral Clustering: Analysis and an Algorithm, Proc. 14th Advances in Neural Information Processing Systems (NIPS '01).
- King,Andrew Douglas2004. Graph Clustering with Restricted Neighbourhood Search, M. S Thesis, University of Toronto.
- Dongen,S. M. van 2002. Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht.
- Glover,F. 1989. Tabu search, part I. ORSA Journal on Computing, 1(3):190-206, summer.
- Mladenovi´c,N. and Hansen,P. 1997. Variable neighbourhood search, Computers and Operations Research, 24(11):1097–1100.
- Dongen, S. M. van 2000. A cluster algorithm for graphs,Technical Report INS-R0010, Centrum voorWiskunde en Informatica.
- Penrose, M. D. 2003. Random Geometric Graphs, Oxford Studies in Probability, OxfordU. P.
- Newman, MEJ and Girvan, M. 2004. Finding and evaluating community structure in networks, Physical Review E, 69, 026113–026127.
- Strehl, A. and Ghosh,J. 2002. Cluster ensembles - a knowledge reuse framework for combining partitionings, AAAI, 93–98.
- Von Mering,C. , Krause,R. , Snel,B. , Cornell,M. , Oliver,S. G. , Fields,S. and Bork, P. 2002. Comparative assessment of large-scale data sets of protein-protein interactions. Nature, 417, 399-403.
Index Terms
Keywords