Call for Paper - January 2023 Edition
IJCA solicits original research papers for the January 2023 Edition. Last date of manuscript submission is December 20, 2022. Read More

Performance Analysis of Molecular Complex Detection in Social Network Datasets

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Authors:
Neny Sulistianingsih, Edi Winarko
10.5120/ijca2017915509

Neny Sulistianingsih and Edi Winarko. Performance Analysis of Molecular Complex Detection in Social Network Datasets. International Journal of Computer Applications 175(4):10-15, October 2017. BibTeX

@article{10.5120/ijca2017915509,
	author = {Neny Sulistianingsih and Edi Winarko},
	title = {Performance Analysis of Molecular Complex Detection in Social Network Datasets},
	journal = {International Journal of Computer Applications},
	issue_date = {October 2017},
	volume = {175},
	number = {4},
	month = {Oct},
	year = {2017},
	issn = {0975-8887},
	pages = {10-15},
	numpages = {6},
	url = {http://www.ijcaonline.org/archives/volume175/number4/28475-2017915509},
	doi = {10.5120/ijca2017915509},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

Researches related graph dataset conducted for years. One of its main topics was community detection. The development of algorithms to do community detection continuously conducted by adjusting characteristics of datasets used. One of which is Molecular Complex Detection (MCODE) algorithm used to community detection in a dataset of protein-protein interaction (PPI). However, use of the algorithm still limited to PPI dataset only. The aim of this research was to conducted experiment usage of MCODE algorithm in other datasets such us social network datasets. An experiment conducted by comparing the performance of MCODE with other benchmark algorithms such us Label Propagation and Girvan-Newman. From the experiment performed was resulted that for modularity MCODE showed the best result when compared with others, followed Girvan-Newman and Label Propagation with its values were 0.67, 0.66 and 0.46, respectively. Furthermore, for a testing parameter such us running time and average clustering coefficient, MCODE showed better result compared with Girvan-Newman and Label Propagation. For running time, MCODE needed mean time as 0.053 s, Girvan-Newman as 0.056 s and Label Propagation as 0.078 s and for test parameter of average clustering coefficient, MCODE was 0.37, Girvan-Newman was 0.44 and Label Propagation was 0.46.

References

  1. M. Girvan and M. E. J. Newman, “Community structure in social and biological networks.,” Proc. Natl. Acad. Sci. U. S. A., vol. 99, no. 12, pp. 7821–6, 2002.
  2. U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Phys. Rev. E - Stat. Nonlinear, Soft Matter Phys., vol. 76, no. 3, pp. 1–12, 2007.
  3. A. Clauset, M. E. J. Newman, and C. Moore, “2004_Clauset_Finding community structure in very large networks.pdf.” Pysichal review, pp. 1–6, 2004.
  4. J. Macqueen, “Some methods for classification and analysis of multivariate observations,” Proc. Fifth Berkeley Symp. Math. Stat. Probab., vol. 1, no. 233, pp. 281–297, 1967.
  5. J. C. Bezdek, R. Ehrlich, and W. Full, “FCM: The fuzzy c-means clustering algorithm,” Comput. Geosci., vol. 10, no. 2–3, pp. 191–203, 1984.
  6. G. D. Bader and C. W. Hogue, “An automated method for finding molecular complexes in large protein interaction networks,” BMC Bioinformatics, vol. 4, no. 1, p. 2, 2003.
  7. P. O’Driscoll, E. Merényi, C. Karmonik, and R. Grossman, “SOM and MCODE methods of defining functional clusters in MRI of the brain,” Conf. Proc. ... Annu. Int. Conf. IEEE Eng. Med. Biol. Soc. IEEE Eng. Med. Biol. Soc. Annu. Conf., vol. 2014, pp. 734–737, 2014.
  8. S. Brohée and J. van Helden, “Evaluation of clustering algorithms for protein-protein interaction networks.,” BMC Bioinformatics, vol. 7, p. 488, 2006.
  9. J. Zhong, L. Liu, Y. Wei, D. Luo, L. Sun, and Y. Lu, “Personalized activity recognition using molecular complex detection clustering,” Ubiquitous Intell. Comput. 2014 IEEE 11th Intl Conf IEEE 11th Intl Conf Auton. Trust. Comput. IEEE 14th Intl Conf Scalable Comput. Commun. Its Assoc. Work., pp. 850–854, 2014.
  10. M. E. J. Newman, “Detecting community structure in networks,” Eur. Phys. J. B - Condens. Matter Complex Syst., vol. 38, no. 2, pp. 321–330, 2004.
  11. T. Matijevi and T. Vujičić, “Performance Analysis of Girvan-Newman Algorithm on Different Types of Random Graphs,” pp. 11–16, 2016.
  12. D. Yanrui, Z. Zhen, W. Wenchao, and C. Yujie, “Identifying the Communities in the Metabolic Network Using ‘Component’ Definition and Girvan-Newman Algorithm,” 2015 14th Int. Symp. Distrib. Comput. Appl. Bus. Eng. Sci., pp. 42–45, 2015.
  13. B. Kong, L. Zhou, and W. Liu, “Improved modularity based on girvan-newman modularity,” Proc. - 2012 Int. Conf. Intell. Syst. Des. Eng. Appl. ISDEA 2012, pp. 293–296, 2012.
  14. L. Despalatović, T. Vojković, and D. Vukičević, “Community structure in networks: Girvan-Newman algorithm improvement,” 2014 37th Int. Conv. Inf. Commun. Technol. Electron. Microelectron. MIPRO 2014 - Proc., no. May, pp. 997–1002, 2014.
  15. A. Lakhdari, A. Chorana, H. Cherroun, and A. Rezgui, “A link strength based label propagation algorithm for community detection,” Proc. - 2016 IEEE Int. Conf. Big Data Cloud Comput. BDCloud 2016, Soc. Comput. Networking, Soc. 2016 Sustain. Comput. Commun. Sustain. 2016, pp. 362–369, 2016.
  16. Z.-W. Liang, J.-P. Li, F. Yang, and A. Petropulu, “Detecting community structure using label propagation with consensus weight in complex network,” Chinese Phys. B, vol. 23, no. 9, p. 98902, 2014.
  17. A. K. K. C., L. Jacques, and C. De Vleeschouwer, “Discriminative and Efficient Label Propagation on Complementary Graphs for Multi-Object Tracking,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 8828, no. c, pp. 1–1, 2015.
  18. Y. He, J. Xu, and B. Yuan, “Community Structure Analysis Using Label Propagation and Flow-Based Ensemble Learning,” pp. 720–726, 2016.
  19. T. Swearingen and A. Ross, “Predicting Missing Demographic Information in Biometric Records using Label Propagation Techniques,” 2016.
  20. G. Liu, K. Meng, H. Guo, L. Pan, and J. Li, “Automatic Threshold Calculation Based Label Propagation Algorithm for Overlapping Community,” 2016 IEEE First Int. Conf. Data Sci. Cybersp., pp. 382–387, 2016.
  21. D. E. Knuth, The Stanford GraphBase : a platform for combinatorial computing. Boston, 2009.
  22. W. W. Zachary, “An Information Flow Model for Conflict and Fission in Small Groups,” J. Anthropol. Res., vol. 33, no. 4, pp. 452–473, 1977.
  23. D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, “The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations,” Behav. Ecol. Sociobiol., vol. 54, no. 4, pp. 396–405, Sep. 2003.
  24. V. Krebs, “Political Books -- Polarized Readers -- May 2004,” 2004. [Online]. Available: http://www.orgnet.com/divided3.html. [Accessed: 05-Jun-2017].
  25. M. E. J. Newman, “Finding community structure in networks using the eigenvectors of matrices,” Phys. Rev. E - Stat. Nonlinear, Soft Matter Phys., vol. 74, no. 3, 2006.
  26. M. Chen and B. K. Szymanski, “Fuzzy Overlapping Community Quality Metrics,” Soc. Netw. Anal. Min., vol. 540, 2015.

Keywords

Community Detection, Girvan-Newman, Molecular Complex Detection, Label Propagation.