We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Advanced Cost based Graph Clustering Algorithm for Random Geometric Graphs

by Mousumi Dhara, K. K. Shukla
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 60 - Number 4
Year of Publication: 2012
Authors: Mousumi Dhara, K. K. Shukla
10.5120/9681-4111

Mousumi Dhara, K. K. Shukla . Advanced Cost based Graph Clustering Algorithm for Random Geometric Graphs. International Journal of Computer Applications. 60, 4 ( December 2012), 20-34. DOI=10.5120/9681-4111

@article{ 10.5120/9681-4111,
author = { Mousumi Dhara, K. K. Shukla },
title = { Advanced Cost based Graph Clustering Algorithm for Random Geometric Graphs },
journal = { International Journal of Computer Applications },
issue_date = { December 2012 },
volume = { 60 },
number = { 4 },
month = { December },
year = { 2012 },
issn = { 0975-8887 },
pages = { 20-34 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume60/number4/9681-4111/ },
doi = { 10.5120/9681-4111 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:05:45.180206+05:30
%A Mousumi Dhara
%A K. K. Shukla
%T Advanced Cost based Graph Clustering Algorithm for Random Geometric Graphs
%J International Journal of Computer Applications
%@ 0975-8887
%V 60
%N 4
%P 20-34
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

There is an increasing interest in the research of clustering or finding communities in complex networks. Graph clustering and graph partitioning algorithms have been applied to this problem. Several graph clustering methods are come into the field but problem lies in the model espoused by the state-of-the-art graph clustering algorithms for solving real-world situation. In this work, an attempt is made to provide an advanced cost based graph clustering algorithm based on stochastic local search. The proposed algorithm delivers significant improvement in robustness and quality of clustering in case of real-world complex network problems. The approach is to compute the cost (scaled cost) accurately when a target node is moved from source to destination cluster. The accurate cost is obtained by computing the induced effect which is evaluated by considering the relevance of nodes related to both source and destination clusters other than the target node during clustering. In our algorithm, moves are only made if the target node has neighbouring nodes in the destination cluster (moves to an empty cluster are the only exception to this instruction). Another important attachment in our approach is in inclusion of the aspiration criteria for the best move (lower-cost changes) selection when the best non-tabu move contributes much higher cost compared to a tabued move then the tabued move is acceptable otherwise the best non-tabu move is approved. Extensive experimentation with synthetic and real random geometric graph (RGG) benchmark datasets show that our algorithm outperforms state-of-the-art graph clustering techniques on the basis of cost of clustering, cluster size, normalized mutual information (NMI) and modularity index of clustering results.

References
  1. Barabási , A. L. , Albert, R. , 2002. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 0034-6861, 47.
  2. Dorogovtsev, S. N. , Mendes, J. F. F. 2003. Evolution of Networks: From Biological Nets to the Internet and WWW, Oxford University Press.
  3. Boccaletti , S. , et al. , Complex networks: Structure and dynamics - FTP Directory Listing. 2006. Phys. Rep. 424 , 175, 175–308.
  4. Newman, M. E. J. 2003. The structure and function of complex networks. SIAM Rev. 45, 167, 167-256.
  5. Watts, D. J. 2004. The "New" Science of Networks. Annu. Rev. Soc. 30, 243, 243-270.
  6. Rapoport, A. , Horvath, W. J. 1961. A study of a large sociogram, Behavioral Science 6,279–291.
  7. Yu, Z. , Wong, H. S. , Wang, H. 2007. Graph-based consensus clustering for class discovery from gene expression data, Bioinformatics 23, 2888–2896.
  8. Bandyopadhyay, S. , Mukhopadhyay, A. , Maulik, U. 2007. An improved algorithm for clustering gene expression data, Bioinformatics 23, 2859–2865.
  9. Barabasi, A. -L. , Albert, R. , Jeong, H. 2000. Scale-free characteristics of random networks: the topology of the World-Wide Web, Physica A: Statistical Mechanics and its Applications 281 (1–4), 69–77.
  10. Kleinberg, J. M. , Kumar, R. , Raghavan, P. , Rajagopalan, S. , Tomkins, A. S. 1999. The Web as a graph: measurements, models, and methods. Computing and Combinatorics: 5th Annual International Conference, COCOON'99, Proceedings, Tokyo, Japan, pp. 1–17.
  11. Kumar, R. , Raghavan, P. , Rajagopalan, S. , Sivakumar, D. , Tomkins, A. , Upfal, E. 2000. Stochastic models for the Web graph. FOCS'00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA, p. 57.
  12. Adamic, L. A. , Huberman, B. A. 2000. Power-law distribution of the World Wide Web. Science 287, 2115.
  13. Newman, M. E. J. , Strogatz, S. H. , Watts, D. J. 2001. Random graphs with arbitrary degree distributions and their applications, Physical Review E 64 (026118).
  14. Watts, D. J. , Strogatz, S. H. 1998. Collective dynamics of 'small-world' networks. Nature 393 (6684) 440–442.
  15. White, J. G. , Southgate, E. , Thomson, J. N. , Brenner, S. 1986. The structure of the nervous system of the nematode Caenorhabditis elegans. Philosophical Transactions of the Royal Society of London Series B-Biological Sciences 314 (1165) 1–340.
  16. Camacho, J. , Guimera, R. , Amaral, L. 2002. Robust patterns in food Web structure. Physical Review Letters 88 (22).
  17. Guelzim, N. , Bottani, S. , Bourgine, P. , Kepes, F. 2002. Topological and causal structure of the yeast transcriptional regulatory network, Nature Genetics 31, 60–63.
  18. Barabási, A. L. , Albert, R. 1999. Emergence of Scaling in Random Networks. Science 286, 509-512.
  19. Milo, R. , Shen-Orr, S. , Itzkovitz, S. , Kashtan, N. , Chklovskii, D. , Alon, U. 2002. Network Motifs: Simple Building Blocks of Complex Networks. Science 298, 824-827.
  20. Alon, U. 2007. The impact of cellular networks on disease comorbidity. Nat. Rev. Gen. 8, 450-461.
  21. Ravasz, E. , Somera, A. L. , Mongru, D. A. , Oltvai, Z. N. , Barabasi, A. -L. 2002. Hierarchical Organization of Modularity in Metabolic Networks. Science 297, 1551-1555.
  22. Brandes, U. , Math , J. 2001. A Faster Algorithm for Betweenness Centrality. Sociol. 25, 163-177.
  23. Holme, P. , Kim, BJ, Yoon, CN, Han, SK. 2002. Attack vulnerability of complex networks, Phys. Rev. E 65, 056109.
  24. Duncan, S. Callaway, John, Hopcroft, E. , Kleinberg, Jon M. , Newman, M. E. J. , and Strogatz, Steven H. 2001. Are randomly grown graphs really random? Physical Review E, 64:041902.
  25. B´ela Bollob´as. 1985. Random Graphs. Academic Press.
  26. Kirkpatrick, Scott and Selman, Bart. 1994. Critical behavior in the satisfiability of random boolean expressions. Science, 264:1297– 1301.
  27. Gilbert, E. N. 1961. Random Plane Networks. Journal of the Society for Industrial and Applied Mathematics, 9(4):533–543.
  28. Watts, Duncan J. and Strogatz, Steven H. 1998. Collective dynamics of 'small-world' networks. Nature, 393(4):440–442.
  29. Newman, M. , Watts, D, and Strogatz, S. 2002. Random graph models of social networks. In Proc. Natl. Acad. Sci, volume 99, pp. 2566–2572.
  30. Barabasi Albert-Laszlo, Crandall, R. E. 2003. Linked: The New Science of Networks. American Journal of Physics, 71(4):409–410.
  31. Penrose, Mathew D. 2003. Random Geometric Graphs. volume 5 of Oxford Studies in Probability. Oxford University Press.
  32. Cohen, Reuven, Erez, Keren, Avraham, Daniel, ben and Havlin, Shlomo. 2000. Resilience of the Internet to Random Breakdowns. Physical Review Letters, 85:4626–4628.
  33. Albert, R´eka. 2000. Hawoong Jeong, and Albert- L´aszl´o Barab´asi. Error and attack tolerance of complex networks. Nature, 406:378–382.
  34. Krapivsky, P. L. , Redner, S. , and Leyvraz, F. 2000. Connectivity of Growing Random Networks. Physical Review Letters, 85:4629– 4632.
  35. Albert, R´eka and Barab´asi, Albert-L´aszl´o. 2000. Topology of Evolving Networks: Local Events and Universality. Physical Review Letters, 85:5234–5237.
  36. Dorogovtsev, S. N. and Mendes, J. F. F. 2000. Evolution of networks with aging of sites. Physical Review E, 62:1842–1845.
  37. Watts, Duncan J. and Strogatz, Steven H. 1998. Collective dynamics of 'small-world' networks. Nature, 393:440–442.
  38. Watts, D. J. 1999. Small Worlds. Princeton University Press.
  39. Newman, M. E. J. and Watts, D. J. 1999. Scaling and percolation in the small-world network model. Physical Review E, 60:7332–7342.
  40. Newman, M. E. J. 2000. Models of the small world. Journal of Statistical Physics, 101:819–841.
  41. Banavar, Jayanth R. , Maritan, Amos, and Rinaldo, Andrea. 1999. Size and form in efficient transportation networks. Nature, 399:130– 132.
  42. Xia, W. and Thorpe, M. F. 1988. Percolation properties of random ellipses. Physical Review A, 38(5):2650–2656.
  43. Balberg, I. 1985. Universal percolationthreshold limits in the continuum. Physical Review B, 31:4053–4055.
  44. Jund, Philippe, Jullien, R´emi, and Campbell, Ian. 2001. Random walks on fractals and stretched exponential relaxation. Physical Review E, 63:036131.
  45. Pastor-Satorras, Romualdo and Vespignani, Alessandro. 2001. Epidemic Spreading in Scale- Free Networks. Physical Review Letters, 86:3200–3203.
  46. 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.
  47. Hall, K. M. 1970. An R-Dimensional Quadratic Placement Algorithm. Management Science, vol. 11, no. 3, pp. 219-229.
  48. 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).
  49. King, Andrew Douglas. 2004. Graph Clustering with Restricted Neighbourhood Search, M. S Thesis, University of Toronto.
  50. Dongen, S. M. van. 2002. Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht.
  51. Glover, F. 1989. Tabu search, part I. ORSA Journal on Computing, 1(3):190-206.
  52. Mladenovi´c, N. and Hansen , P. 1997. Variable neighbourhood search, Computers and Operations Research, 24(11):1097–1100.
  53. NEWMAN, M. E. J. AND GIRVAN, M. 2004. Finding and evaluating community structure in networks. Physical Review E 69, 026113.
  54. Kvalseth, T. O. , 1987. Entropy and correlation: Some comments. Systems, Man and Cybernetics, IEEE Transactions, 17(3):517–519.
  55. 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.
  56. Shai S. Shen-Orr, Ron Milo, Shmoolik Mangan & Uri Alon. (2002) Network motifs in the transcriptional regulation network of Escherichia coli. Nature 31,64-68.
  57. Dhara, Mousumi and Shukla, K. K. . 2012. Performance Testing of RNSC and MCL Algorithms on Random Geometric Graphs. International Journal of Computer Applications (0975 – 8887) Volume 53– No. 12.
Index Terms

Computer Science
Information Sciences

Keywords

RGG Cost of clustering Cluster size Normalized mutual information (NMI) and Modularity index of clustering results

Powered by PhDFocusTM