Please wait a minute...
Big Data Mining and Analytics  2018, Vol. 01 Issue (03): 245-256    DOI: 10.26599/BDMA.2018.9020023
    
A Multi-granularity Decomposition Mechanism of Complex Tasks Based on Density Peaks
Ziling Pang, Guoyin Wang*, Jie Yang
Ziling Pang, Guoyin Wang, and Jie Yang are with the Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Post and Telecommunication, Chongqing 400060, China. E-mail: woshi@pangziling.com; 530966074@qq.com.
Download: PDF (1524 KB)      HTML  
Export: BibTeX | EndNote (RIS)      

Abstract  

There are many algorithms for solving complex problems in supervised manner. However, unsupervised tasks are more common in real scenarios. Inspired by the idea of granular computing and the characteristics of human cognitive process, this paper proposes a complex tasks decomposition mechanism based on Density Peaks Clustering (DPC) to address complex tasks with an unsupervised process, which simulates the multi-granular observation and analysis of human being. Firstly, the DPC algorithm is modified to nullify its essential defects such as the difficulty of locating correct clustering centers and classifying them accurately. Then, the improved DPC algorithm is used to construct the initial decomposition solving space with multi-granularity theory. We also define subtask centers set and the granulation rules to guide the multi-granularity decomposing procedure. These rules are further used to decompose the solving space from coarse granules to the optimal fine granules with a convergent and automated process. Furthermore, comprehensive experiments are presented to verify the applicability and veracity of our proposed method in community-detection tasks with several benchmark complex social networks. The results show that our method outperforms other four state-of-the-art approaches.



Key wordsmulti-granularity      task decomposition      density peaks      complex network     
Received: 08 September 2017      Published: 13 January 2020
Corresponding Authors: Guoyin Wang   
Cite this article:

Ziling Pang, Guoyin Wang, Jie Yang. A Multi-granularity Decomposition Mechanism of Complex Tasks Based on Density Peaks. Big Data Mining and Analytics, 2018, 01(03): 245-256.

URL:

http://bigdata.tsinghuajournals.com/10.26599/BDMA.2018.9020023     OR     http://bigdata.tsinghuajournals.com/Y2018/V01/I03/245

Fig. 1 (a) Dataset DS which contains the latitude and longitude of 13 cities; (b) Leading tree of DS; and (c) Clustering result of DS.
iNneighiC?L
1121
2131
3121
4121
562
6132
782
862
9113
10113
11123
12131
1301
Table 1 The intermediate results of DS.
Fig. 2 The real social structure of Dolphin network.
iδiρiNneighi
12.210.7548
22.420.7955
31.080.8111
40.920.7960
311.760.7348
320.201.0018
620.6011.0038
Table 2 The intermediate results of DPC in Dolphin network.
Fig. 3 The global task leading tree of Dolphin network.
iδiρiNneighio?r?d?γi
12.210.754846
22.420.795515
31.080.811114
40.920.796038
34
311.760.734852
320.20118
620.6113861
Table 3 The redundant centers CT of Dolphin network.
iSimilarity (i)
46
150.436
140.129
380.291
340.290
520.290
Table 4 Popping process for the first member of final center task set.
Fig. 4 (a) Global leading tree structure of Dolphin network; (b) Progress of the first granulation, where node 14 is one of the community center, so the tree splits two sub trees, and they are constituted as a fine granularity task solving layer; (c) Granulating process triggered by center node 52, and they form a fine granular solving layer with three subtask sets.
iSimilarity (i)
46
150.559
380.500
340.529
520.317
Table 5 Popping process for the second member of final center task set.
iSimilarity (i)
46
150.559
380.500
340.529
Table 6 Popping process for the third member of final center task set.
Fig. 5 The structure of Dolphin network by MrGDM.
MethodDescription
ENBC[28]By utilizing personal views and redefined community structure, this algorithm presents a notion of common interest in the relationship of social network. The method proposes two key measures reachability and isolability, where the reachability evaluates the ability of each node to reach out members of community and the isolability accounts for the ability of any community to isolate itself from the rest of the network.
Local-T[29]By considering the number of internal and external triads, the main idea of this method is the T metric, which computes the relative quality of a community. The authors propose an intuitive statistical method based on the T metric, which can identify outlier and hub nodes within each discovered community.
CDERS[30]The authors utilize an expanding ring search starting from the individual of interest and treat it as the seed node, and then according to their definition of a community, they iteratively contain the nodes at increasing number of hops from the seed user. If there is no further nodes can be appended, the iterative process is terminated. Furthermore, the social communities are organized by the list of added nodes.
LICOD[31]This method adopts a leader-follower approach, whereby the leader nodes create social communities in which local communities can be calculated. The nodes whose degree is higher percentage compared to their neighbors would be selected as leader nodes. And then the leaders with a certain percent of common neighbors are considered a community. By computing the shortest distance of every node to the leader and considering the decision of neighbors, each node can be added to advisable community.
Table 7 Compared methods and their description.
DatasetMethodNMIF-ScoreModularity (rank)C
Karate0.3582
ENBC0.8370.9390.3582
Local-T0.8370.9390.3722
LICOD0.6770.8820.3722
CDERS0.6490.8320.3122
MrGDM1(1)1(1)0.371 (2)2
Dolphin0.3602
ENBC0.5300.6710.4913
Local-T0.4340.6050.5104
LICOD0.4420.4710.4947
CDERS0.6270.8900.3742
MrGDM0.889 (1)0.970 (1)0.379 (2)2
Football0.55112
ENBC0.9060.8100.59210
Local-T0.8640.7220.54510
LICOD0.9000.8500.60311
CDERS0.7620.6440.63412
MrGDM0.890 (3)0.829 (2)0.555 (1)12
LFR10.78415
ENBC0.9920.9920.78115
Local-T0.9920.9920.78115
LICOD0.9650.9220.77713
CDERS0.9220.8670.63415
MrGDM0.970 (3)1 (1)0.857 (4)15
LFR20.85930
ENBC0.9980.9970.85830
Local-T0.7770.5040.70619
LICOD0.9970.9950.85331
CDERS0.9420.9130.78030
MrGDM0.959 (3)0.957 (3)0.837 (3)31
Table 8 Experimental applications of the compared methods for the selected datasets.
AlgorithmComplexityRemark
ENBC[28]O?(n2)Accurate communities, but still bound by cost
Local-T[29]O?(n3)Identifies outliers, but for local communities
CDERS[30]O?(n2)Accurate communities in small network
LICOD[[31]O?(n3)Smaller and very inaccurate communities
SCAN[38]O?(m)Identifies outliers, but inaccurate communities
LeadF[39]O?(nm)Smaller communities in dense network
MrGDMO?(n2)Accurate communities, but for dense network
Table 9 Summary of complexity of community detection algorithms.
[1]   Hobbs J. R., Granularity, in Readings in Qualitative Reasoning about Physical Systems, Weld D. S. and De Kleer J., eds. Elsevier, 1990, pp. 542-545.
[2]   Zhang L. and Zhang B., Theory and Application of Problem Solving. Beijing, China: Tsinghua University Press, 1990.
[3]   Jang J. S. R., ANFIS: Adaptive-network-based fuzzy inference system, IEEE Trans. Syst., Man, and Cybern., vol. 23, no. 3, pp. 665-685, 1993.
[4]   Wang G. Y. and Shi H. B., TMLNN: Triple-valued or multiple-valued logic neural network, IEEE Trans. Neural Netw., vol. 9, no. 6, pp. 1099-1117, 1998.
[5]   Zhu L. Y., Yuan G. W., and Du Q., An efficient explicit/implicit domain decomposition method for convection-diffusion equations, Numer. Methods Partial Differ. Equ., vol. 26, no. 4, pp. 852-873, 2010.
[6]   Jenkins R. E. and Yuhas B. P., A simplified neural network solution through problem decomposition: The case of the truck backer-upper, IEEE Trans. Neural Netw., vol. 4, no. 4, pp. 718-720, 1993.
[7]   Thiria S., Mejia C., Badran F., and Crépon M., Multimodular architecture for remote sensing operations, in Proc. 4th Int. Conf. Neural Information Processing Systems, Denver, CO, USA, 1991, pp. 675-682.
[8]   Rifkin R. and Klautau A., In defense of one-vs-all classification, J. Mach. Learn. Res., vol. 5, pp. 101-141, 2004.
[9]   Perdisci R., Gu G. F., and Lee W., Using an ensemble of one-class SVM classifiers to harden payload-based anomaly detection systems, in Proc. 6th Int. Conf. Data Mining, Hong Kong, China, 2006, pp. 488-498.
[10]   Cobo L. C., Isbell C. L. Jr., and Thomaz A. L., Automatic task decomposition and state abstraction from demonstration, in Proc. 11th Int. Conf. Autonomous Agents and Multiagent Systems, Valencia, Spain, 2012, pp. 483-490.
[11]   Xu J. and Wang G. Y., Leading tree in DPCLUS and its impact on building hierarchies, arXiv preprint arXiv: 1506.03879, 2015.
[12]   Rodriguez A. and Laio A., Clustering by fast search and find of density peaks, Science, vol. 344, no. 6191, pp. 1492-1496, 2014.
[13]   Sun K., Geng X. R., and Ji L. Y., Exemplar component analysis: A fast band selection method for hyperspectral imagery, IEEE Geosci. Remote Sens. Lett., vol. 12, no. 5, pp. 998-1002, 2015.
[14]   Chen Y. W., Lai D. H., Qi H., Wang J. L., and Du J. X., A new method to estimate ages of facial image for large database, Multimed. Tools Appl., vol. 75, no. 5, pp. 2877-2895, 2016.
[15]   Wu H. and Wan Y., Clustering assisted fundamental matrix estimation, arXiv preprint arXiv: 1504.03409, 2015.
[16]   Dean K. M., Davis L. M., Lubbeck J. L., Manna P., Friis P., Palmer A. E., and Jimenez R., High-speed multiparameter photophysical analyses of fluorophore libraries, Anal. Chem., vol. 87, no. 10, pp. 5026-5030, 2015.
[17]   Zeng A. P. and Huang Y. P., A text classification algorithm based on Rocchio and hierarchical clustering, in Proc. 7th Int. Conf. Advanced Intelligent Computing, Zhengzhou, China, 2011, pp. 432-439.
[18]   Wang M. M., Zuo W. L., and Wang Y., An improved density peaks-based clustering method for social circle discovery in social networks, Neurocomputing, vol. 179, pp. 219-227, 2016.
[19]   He W. and Xing M. D., Classification method for POLSAR images based on find of density peak, (in Chinese), Syst. Eng. Electron., vol. 38, no. 1, pp. 60-63, 2016.
[20]   Xu J., Wang G. Y., and Deng W. H., DenPEHC: Density peak based efficient hierarchical clustering, Inf. Sci., vol. 373, pp. 200-218, 2016.
[21]   Wang G. Y., Xu J., Zhang Q. H., and C Liu Y., Multi-granularity intelligent information processing, in Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, Yao Y. Y., Hu Q. H., Yu H., and Grzymala-Busse J. W., eds. Springer, 2015.
[22]   Wang S. L., Wang D. K., Li C. Y., Li Y., and Ding G. Y., Clustering by fast search and find of density peaks with data field, Chin. J. Electron., vol. 25, no. 3, pp. 397-402, 2016.
[23]   Qiu T., Yang K. F., Li C. Y., and Li Y. J., A physically inspired clustering algorithm: To evolve like particles, arXiv preprint arXiv: 1412.5902, 2014.
[24]   Du M. L., Ding S. F., and Jia H. J., Study on density peaks clustering based on k-nearest neighbors and principal component analysis, Knowl.-Based Syst., vol. 99, pp. 135-145, 2016.
[25]   Xu X. H., Ju Y. S., Liang Y. L., and He P., Manifold density peaks clustering algorithm, in Proc. 3rd Int. Conf. Advanced Cloud and Big Data, Yangzhou, China, 2015, pp. 311-318.
[26]   Zhang W. K. and Li J., Extended fast search clustering algorithm: Widely density clusters, no density peaks, arXiv preprint arXiv: 1505.05610, 2015.
[27]   Karypis G., Han E. H., and Kumar V., Chameleon: Hierarchical clustering using dynamic modeling, Computer, vol. 32, no. 8, pp. 68-75, 1999.
[28]   Biswas A. and Biswas B., Investigating community structure in perspective of ego network, Expert Syst. Appl., vol. 42, no. 20, pp. 6913-6934, 2015.
[29]   Fagnan J., Za?ane O., and Barbosa D., Using triads to identify local community structure in social networks, in Proc. 2014 IEEE/ACM Int. Conf. Advances in Social Networks Analysis and Mining, Beijing, China, 2014, pp. 108-112.
[30]   Lim K. H. and Datta A., A seed-centric community detection algorithm based on an expanding ring search, in Proc. 1st Australasian Web Conf., Adelaide, South Australia, 2013.
[31]   Yakoubi Z. and Kanawati R., LICOD: A leader-driven algorithm for community detection in complex networks, Vietnam J. Comput. Sci., vol. 1, no. 4, pp. 241-256, 2014.
[32]   Lusseau D., Schneider K., Boisseau O. J., Haase P., Slooten E., and Dawson S. M., 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, 2003.
[33]   Zachary W. W., An information flow model for conflict and fission in small groups, J. Anthropol. Res., vol. 33, no. 4, pp. 452-473, 2015.
[34]   Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA, vol. 99, no. 12, pp. 7821-7826, 2002.
[35]   Lancichinetti A., Fortunato S., and Radicchi F., Benchmark graphs for testing community detection algorithms, Phys. Rev. E, vol. 78, no. 4, 2008.
[36]   Vinh N. X., Epps J., and Bailey J., Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance, J. Mach. Learn. Res., vol. 11, pp. 2837-2854, 2010.
[37]   Tabarzad M. A. and Hamzeh A., A heuristic local community detection method (HLCD), Appl. Intell., vol. 46, no. 1, pp. 62-78, 2017.
[38]   Xu X. W., Yuruk N., Feng Z. D., and Schweiger T. A. J., SCAN: A structural clustering algorithm for networks, in Proc. 13th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Jose, CA, USA, 2007, pp. 824-833.
[39]   Shah D. and Zaman T., Community detection in networks: The leader-follower algorithm, arXiv preprint arXiv: 1011.0774 , 2010.
No related articles found!