Detecting and refining overlapping regions in complex networks with three-way decisions. (English) Zbl 1429.68245
Summary: The identification of communities is crucial to an understanding of the structural and functional properties of a complex network. Many methods and algorithms have been developed to detect overlapping communities. A problem that has not been addressed satisfactorily is the relationship or difference between vertices in overlapping regions during the formation and growth of communities. This paper investigates methods that not only detect the overlapping communities but also refine the overlapping regions. We give a three-way representation of a community by using interval sets and re-formalize the problem of community detection as three-way clustering. We suggest four macro types and eight micro types of vertices to characterize members in overlapping regions for their refinement. We propose an overlapping community detection algorithm by classifying the vertices into core vertices, bone vertices, and trivial vertices. The main strategy of this algorithm is to find an initial cluster core, to expand the core to a preliminary community according to a new fitness function, and to merge trivial vertices based on three-way decision strategies. The experimental results on both real-world social networks and computer-generated artificial networks show the effectiveness and efficiency of the proposed methods.
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
References:
| [1] | Ahn, Y. Y.; Bagrow, J. P.; Lehmann, S., Link communities reveal multiscale complexity in networks, Nature, 466, 7307, 761-764 (2010) |
| [2] | Baumes, J.; M. Goldberg; Krishnamoorthy, M.; Magdon-Ismail, M.; Preston, N., Finding communities by clustering a graph into overlapping subgraphs, Proceedings of the IADIS international conference on applied computing, 7, 97-104 (2005) |
| [3] | Mu, C.; Liu, Y.; Liu, Y.; Wu, J. S.; Jiao, L. C., Two-stage algorithm using influence coefficient for detecting the hierarchical, non-overlapping and overlapping community structure, Physica A, 408, 47-61 (2014) · Zbl 1395.05162 |
| [4] | Coscia, M.; Giannotti, F.; Pedreschi, D., A classification for community discovery methods in complex networks, Stat. Anal. Data Min., 4, 5, 512-546 (2011) · Zbl 07260300 |
| [5] | Evans, T. S.; Lambiott, R., Line graphs, link partitions and overlapping communities, Phys. Rev. E, 80, 1, 016105:1-016105:8 (2009) |
| [6] | Fortunato, S., Community detection in graphs, Phys. Rep., 486, 3-5, 75-174 (2010) |
| [7] | Goudey, R., Do statistical inferences allowing three alternative decisions give better feedback for environmentally precautionary decision-making?, J. Environ. Manag., 85, 2, 338-344 (2007) |
| [8] | Huang, J. B.; Sun, H. L.; Han, J. W.; Feng, B. Q., Density-based shrinkage for revealing hierarchical and overlapping community structure in networks, Physica A, 390, 11, 2160-2171 (2011) |
| [9] | Jia, C. Y.; Carson, M. B.; Yu, J., A fast weak motif-finding algorithm based on community detection in graphs, BMC Bioinf., 227, 14, 1-14 (2013) |
| [10] | Lancichinetti, A.; Fortunato, S.; Kertész, J., Detecting the overlapping and hierarchical community structure in complex networks, New J. Phys., 11, 3, 033015:1-033015:19 (2009) |
| [12] | Lee, C.; Reid, F.; McDaid, A.; Hurley, N., Detecting highly overlapping community structure by greedy clique expansion, SNA-KDD10: Proceedings of the 4th Workshop on Social Network Mining and Analysis, 32-42 (2010) |
| [13] | Li, J. Q.; Wang, X. Y.; Eustace, J., Detecting overlapping communities by seed community in weighted complex networks, Physica A, 392, 23, 6125-6134 (2013) |
| [14] | Liang, D.; Liu, D., Systematic studies on three-way decisions with interval-valued decision-theoretic rough sets, Inf. Sci., 276, 186-203 (2014) |
| [15] | Lusseau, D.; Schneider, K.; Boisseau, O. J.; Haase, P.; Slooten, E.; Dawson, S. M., The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations, Behav. Ecol. Sociobiol., 54, 4, 396-405 (2003) |
| [16] | Meo, P. D.; Ferrara, E.; Fiumara, G.; Provetti, A., Enhancing community detection using a network weighting strategy, Inf. Sci., 222, 648-668 (2013) · Zbl 1293.91164 |
| [17] | Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 2, 167-256 (2003) · Zbl 1029.68010 |
| [18] | Newman, M., Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, 74, 3, 036104:1-036104:22 (2006) |
| [19] | Newman, M., Modularity and community structure in networks, Proceedings of the National Academy of Sciences of the United States of America, 103, 8577-8582 (2006) |
| [20] | Palla, G.; Derényi, I.; Farkas, I.; Vicsek, T., Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435, 7043, 814-818 (2005) |
| [22] | Psorakis, I.; Roberts, S.; Ebden, M.; B. Sheldon, Overlapping community detection using bayesian non-negative matrix factorization, Phys. Rev. E, 83, 6, 066114:1-066114:9 (2011) |
| [23] | Schechter, C. B., Sequential analysis in a bayesian model of diastolic blood pressure measurement, Med. Decis. Making, 8, 3, 191-196 (1988) |
| [24] | Shen, H. W.; Cheng, X. Q.; Cai, K.; Hu, M. B., Detect overlapping and hierarchical community structure in networks, Physica A, 388, 8, 1706-1712 (2009) |
| [25] | Shi, C.; Cai, Y. N.; Fu, D.; Dong, Y. X.; Wu, B., A link clustering based overlapping community detection algorithm, Data Knowl. Eng., 87, 394-404 (2013) |
| [26] | Sun, P. G.; Gao, L.; Han, S. S., Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex networks, Inf. Sci., 181, 6, 1060-1071 (2011) · Zbl 1208.91120 |
| [27] | Wang, X. H.; Jiao, L. C.; Wu, J. S., Adjusting from disjoint to overlapping community detection of complex networks, Physica A, 388, 24, 5045-5056 (2009) |
| [28] | Weller, A. C., Editorial peer review: its strengths and weaknesses (2001), Information Today, Inc. |
| [29] | Xie, J. R.; Kelley, S.; Szymanski, B. K., Overlapping community detection in networks: the state-of-the-art and comparative study, ACM Comput. Surv. (CSUR), 45, 4, 1-35 (2013) · Zbl 1288.68191 |
| [30] | Xie, J. R.; Szymanski, B. K., Towards linear time overlapping community detection in social networks, Advances in Knowledge Discovery and Data Mining - 16th Pacific-Asia Conference, PAKDD 2012, Kuala Lumpur, Malaysia, May 29, - June 1, 2012, Proceedings, Part II, 25-36 (2012) |
| [31] | Yao, J. T.; Azam, N., Web-based medical decision support systems for three-way medical decision making with game-theoretic rough sets, IEEE Trans. Fuzzy Syst., 23, 1, 3-15 (2015) |
| [32] | Yao, Y. Y., Interval-set algebra for qualitative knowledge representation, Proceedings of the 5th International Conference on Computing and Information, 370-375 (1993) |
| [33] | Yao, Y. Y., An outline of a theory of three-way decisions, Rough Sets and Current Trends in Computing, 1-17 (2012), Springer · Zbl 1404.68177 |
| [34] | Yao, Y. Y., Three-way decisions and cognitive computing, Cognit. Comput., 8, 4, 543-554 (2016) |
| [35] | Yu, H.; Jiao, P.; Wang, G. Y.; Yao, Y. Y., Categorizing overlapping regions in clustering analysis using three-way decisions, 2014 IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT), 350-357 (2014) |
| [36] | Yu, H.; Liu, Z. G.; Wang, G. Y., An automatic method to determine the number of clusters using decision-theoretic rough set, Int. J. Approximate Reasoning, 55, 1, 101-115 (2014) · Zbl 1316.68121 |
| [37] | Yu, H.; Wang, G. Y.; Li, T. R.; Liang, J. Y.; Miao, D. Q.; Yao, Y. Y., Three-way decisions: methods and practices for complex problem solving (in Chinese) (2015), Science Press, Beijing, China |
| [38] | Yu, H.; Zhang, C.; Wang, G. Y., A tree-based incremental overlapping clustering method using the three-way decision theory, Knowl.-Based Syst., 91, 1, 189-203 (2016) |
| [39] | Zachary, W. W., An information flow model for conflict and fission in small groups, J. Anthropol. Res., 33, 4, 452-473 (1977) |
| [40] | Zhou, B.; Yao, Y. Y.; Luo, J. G., Cost-sensitive three-way email spam filtering, J. Intell. Inform. Syst., 42, 1, 19-45 (2014) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
