The week's pick
Reseach Article
Performance Analysis of Molecular Complex Detection in Social Network Datasets
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 175 - Number 4 |
| Year of Publication: 2017 |
| Authors: Neny Sulistianingsih, Edi Winarko |
10.5120/ijca2017915509
|
Neny Sulistianingsih, Edi Winarko . Performance Analysis of Molecular Complex Detection in Social Network Datasets. International Journal of Computer Applications. 175, 4 ( Oct 2017), 10-15. DOI=10.5120/ijca2017915509
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
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- S. Brohée and J. van Helden, “Evaluation of clustering algorithms for protein-protein interaction networks.,” BMC Bioinformatics, vol. 7, p. 488, 2006.
- 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.
- 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.
- T. Matijevi and T. Vujičić, “Performance Analysis of Girvan-Newman Algorithm on Different Types of Random Graphs,” pp. 11–16, 2016.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Y. He, J. Xu, and B. Yuan, “Community Structure Analysis Using Label Propagation and Flow-Based Ensemble Learning,” pp. 720–726, 2016.
- T. Swearingen and A. Ross, “Predicting Missing Demographic Information in Biometric Records using Label Propagation Techniques,” 2016.
- 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.
- D. E. Knuth, The Stanford GraphBase : a platform for combinatorial computing. Boston, 2009.
- 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.
- 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.
- V. Krebs, “Political Books -- Polarized Readers -- May 2004,” 2004. [Online]. Available: http://www.orgnet.com/divided3.html. [Accessed: 05-Jun-2017].
- 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.
- M. Chen and B. K. Szymanski, “Fuzzy Overlapping Community Quality Metrics,” Soc. Netw. Anal. Min., vol. 540, 2015.
Index Terms
Keywords