Top

Journal of Intelligent Information Systems

Published in:

16-09-2021

IbLT: An effective granular computing framework for hierarchical community detection

Authors: Shun Fu, Guoyin Wang, Ji Xu, Shuyin Xia

Published in: Journal of Intelligent Information Systems | Issue 1/2022

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Mapping the vertices of network onto a tree helps to reveal the hierarchical community structures. The leading tree is a granular computing (GrC) model for efficient hierarchical clustering and it requires two elements: the distance between granules, and the density calculated in Euclidean space. For the non-Euclidean network data, the vertices need to be embedded in the Euclidean space before density calculation. This results in the marginalization of community centers. This paper proposes a new hierarchical community detection framework, called Importance-based Leading Tree (IbLT). Different from the density-based leading tree, IbLT calculates the structural similarity between vertices and the importance of the vertices respectively. It generates leading trees that match the structural features of the vertices, and thus, IbLT obtains more accurate results for the detection of hierarchical community structures. Experiments are conducted to evaluate the performance of the proposed novel IbLT-based method. On social network community detection task, the quantitative results show that this method achieves competitive accuracy.

previous article Cross-lingual transfer of abstractive summarizer to less-resource language

next article Upper bounds for can-tree and FP-tree

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Balakrishnan, S., Xu, M., Krishnamurthy, A., & et al. (2011). Noise thresholds for spectral clustering. In Proceedings of the 25th advances in neural information processing systems, curran associates, Inc. (pp. 954–962).

Bindu, P., Mishra, R., & Thilagam, P.S. (2018). Discovering spammer communities in twitter. Journal of Intelligent Information Systems, 51(3), 503–527.CrossRef

Blin, L., Awan, A.J., & Heinis, T. (2018). Using neuromorphic hardware for the scalable execution of massively parallel, communication-intensive algorithms. In Proceedings of the 2018 IEEE/ACM international conference on utility and cloud computing companion (UCC Companion) (pp. 89–94). IEEE.

Bryant, A., & Cios, K. (2017). Rnn-dbscan: a density-based clustering algorithm using reverse nearest neighbor density estimates. IEEE Transactions on Knowledge and Data Engineering, 30(6), 1109–1121.CrossRef

Chouchani, N., & Abed, M. (2020). Online social network analysis: detection of communities of interest. Journal of Intelligent Information Systems, 54 (1), 5–21.CrossRef

Clauset, A., Newman, M.E., & Moore, C. (2004). Finding community structure in very large networks. Physical Review E, 70(6), 066111.CrossRef

Danon, L., Diaz-Guilera, A., Duch, J., & et al. (2005). Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 2005(09), P09008.CrossRef

Dasgupta, A., Hopcroft, J., Kannan, R., & et al. (2006). Spectral clustering by recursive partitioning. In Proceedings of the 14th European Symposium on Algorithms (pp. 256–267). Springer.

Ding, Y., Yan, E., Frazho, A., & et al. (2009). Pagerank for ranking authors in co-citation networks. Journal of the American Society for Information Science and Technology, 60(11), 2229–2243.CrossRef

Ester, M., Kriegel, H.P., Sander, J., & et al. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd ACM SIGKDD international conference on knowledge discovery and data mining (pp. 226–231). ACM.

Freeman, L.C. (1978). Centrality in social networks conceptual clarification. Social Networks, 1(3), 215–239.CrossRef

Gao, X., Bao, N., Liu, J., & et al. (2016). Scalable single-source simrank computation for large graphs. In Proceedings of the 2016 IEEE 22nd international conference on parallel and distributed systems (ICPADS), (pp. 1083–1091). IEEE.

Girvan, M., & Newman, M.E. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12), 7821–7826.MathSciNetCrossRef

Gleich, D.F. (2015). Pagerank beyond the web. Siam Review, 57 (3), 321–363.MathSciNetCrossRef

Guha, S., Rastogi, R., & Shim, K. (2000). Rock: a robust clustering algorithm for categorical attributes. Information Systems, 25(5), 345–366.CrossRef

Guha, S., Rastogi, R., & Shim, K. (2001). Cure: an efficient clustering algorithm for large databases. Information Systems, 26(1), 35–58.CrossRef

Hou, J., Gao, H., & Li, X. (2016). Dsets-dbscan: a parameter-free clustering algorithm. IEEE Transactions on Image Processing, 25(7), 3182–3193.MathSciNetCrossRef

Jeh, G., & Widom, J. (2002). Simrank: a measure of structural-context similarity. In Proceedings of the 8th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 538–543). ACM.

Karypis, G., Han, E.H., & Kumar, V. (1999). Chameleon: Hierarchical clustering using dynamic modeling. Computer, 32(8), 68–75.CrossRef

Kleinberg, J. (2001). Small-world phenomena and the dynamics of information. In Proceedings of the 14th international conference on neural information processing systems: natural and synthetic (pp. 431–438). MIT Press.

Kobren, A., Monath, N., Krishnamurthy, A., & et al. (2017). A hierarchical algorithm for extreme clustering. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining (pp. 255–264). ACM.

Kumar, S., Panda, B., & Aggarwal, D. (2020). Community detection in complex networks using network embedding and gravitational search algorithm. Journal of Intelligent Information Systems, 57(1), 51–72.CrossRef

Kusumoto, M., Maehara, T., & Ki, K. (2014). Scalable similarity search for simrank. In Proceedings of the 2014 ACM SIGMOD international conference on management of data (pp. 325–336). ACM.

Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008). Benchmark graphs for testing community detection algorithms. Physical Review E, 78(4), 046110.CrossRef

Li, D., Liu, C., & Gan, W. (2009). A new cognitive model: Cloud model. International Journal of Intelligent Systems, 24(3), 357–375.CrossRef

Lv, Y., Ma, T., Tang, M., & et al. (2016). An efficient and scalable density-based clustering algorithm for datasets with complex structures. Neurocomputing, 171, 9–22.CrossRef

Lyzinski, V., Tang, M., Athreya, A., & et al. (2016). Community detection and classification in hierarchical stochastic blockmodels. IEEE Transactions on Network Science and Engineering, 4(1), 13–26.MathSciNetCrossRef

Mislove, A., Marcon, M., Gummadi, K.P., & et al. (2007). Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM conference on internet measurement (pp. 29–42). ACM.

Moody, J., & White, D.R. (2003). Structural cohesion and embeddedness: a hierarchical concept of social groups. American Sociological Review, 68 (1), 103–127.CrossRef

Murtagh, F., & Contreras, P. (2012). Algorithms for hierarchical clustering: an overview. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2(1), 86–97.

Page, L., Brin, S., Motwani, R., & et al. (1999). The pagerank citation ranking: Bringing order to the web. Tech. rep., Stanford InfoLab.

Pawlak, Z. (1998). Granularity of knowledge, indiscernibility and rough sets. In Proceedings of the 1998 IEEE international conference on fuzzy systems proceedings (pp. 106–110). IEEE.

Pedrycz, W. (2011). The principle of justifiable granularity and an optimization of information granularity allocation as fundamentals of granular computing. Journal of Information Processing Systems, 7(3), 397–412.CrossRef

Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 701–710). ACM.

Pons, P., & Latapy, M. (2005). Computing communities in large networks using random walks. In Proceedings of the 20th international symposium on computer and information sciences (pp. 284–293). Springer.

Qian, Y., Liang, J., Yao, Y., & et al. (2010). Mgrs: a multi-granulation rough set. Information Sciences, 180(6), 949–970.MathSciNetCrossRef

Qinghua Zhang, X.L., & Wang, G. (2008). Hierarchical structure analysis of fuzzy quotient space. Pattern Recognition and Artificial Intelligence [CN], 21 (5), 627–634.

Raghavan, U.N., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3), 036106.CrossRef

Ram, A., Sharma, A., Jalal, A.S., & et al. (2009). An enhanced density based spatial clustering of applications with noise. In Proceedings of 2009 IEEE international advance computing conference (pp. 1475–1478). IEEE.

Sadi, F., Sweeney, J., McMillan, S., & et al. (2018). Pagerank acceleration for large graphs with scalable hardware and two-step spmv. In Proceedings of the 2018 IEEE high performance extreme computing conference (HPEC) (pp. 1–7). IEEE.

Sarma, A.D., Molla, A.R., Pandurangan, G., & et al. (2013). Fast distributed pagerank computation. In Proceedings of the 14th international conference on distributed computing and networking (pp. 11–26). Springer.

Vadapalli, S., Valluri, S.R., & Karlapalem, K. (2006). A simple yet effective data clustering algorithm. In Proceedings of the 6th international conference on data mining (pp. 1108–1112). IEEE.

Wang, G. (2017). Dgcc: data-driven granular cognitive computing. Granular Computing, 2(4), 343–355.CrossRef

Wang, G., Yang, J., & Xu, J. (2017). Granular computing: from granularity optimization to multi-granularity joint problem solving. Granular Computing, 2(3), 105–120.CrossRef

Wang, R., Zhang, W., Deng, H., & et al. (2013). Discover community leader in social network with pagerank. In Proceedings of the 4th international conference in swarm intelligence (pp. 154–162). Springer.

Xu, J., Wang, G., & Deng, W. (2016). Denpehc: Density peak based efficient hierarchical clustering. Information Sciences, 373, 200–218.CrossRef

Xu, J., Wang, G., Li, T., & et al. (2017a). Fat node leading tree for data stream clustering with density peaks. Knowledge-Based Systems, 120, 99–117.CrossRef

Xu, J., Wang, G., Li, T., & et al. (2017b). Local-density-based optimal granulation and manifold information granule description. IEEE Transactions on Cybernetics, 48(10), 2795–2808.CrossRef

Xu, J., Li, T., Wu, Y., & et al. (2021). Lapoleaf: Label propagation in an optimal leading forest. Information Sciences, 575, 133–154.MathSciNetCrossRef

Yang, J., & Leskovec, J. (2015). Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 42(1), 181–213.CrossRef

Yang, Z., Algesheimer, R., & Tessone, C.J. (2016). A comparative analysis of community detection algorithms on artificial networks. Scientific Reports, 6(1), 1–18.CrossRef

Yao, J.T., Vasilakos, A.V., & Pedrycz, W. (2013). Granular computing: perspectives and challenges. IEEE Transactions on Cybernetics, 43(6), 1977–1989.CrossRef

Yao, Y., & Zhao, L. (2012). A measurement theory view on the granularity of partitions. Information Sciences, 213, 1–13.MathSciNetCrossRef

Yao, Y., et al. (2000). Granular computing: basic issues and possible solutions. In Proceedings of the 5th joint conference on information sciences, association for intelligent machinery, pp 186–189.

Young, S.J., & Scheinerman, E.R. (2007). Random dot product graph models for social networks. In Proceedings of the 5th international workshop on algorithms and models for the web-graph (pp. 138–149). Springer.

Yu, W., Lin, X., & Le, J. (2010). Taming computational complexity: Efficient and parallel simrank optimizations on undirected graphs. In Proceedings of the 2010 international conference on web-age information management (pp. 280–296). Springer.

Yu, W., Lin, X., Zhang, W., & et al. (2019). Simrank*: effective and scalable pairwise similarity search based on graph topology. The VLDB Journal, 28(3), 401–426.CrossRef

Zachary, W.W. (1977). An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33(4), 452–473.CrossRef

Zadeh, L.A. (1997). Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic. Fuzzy Sets and Systems, 90 (2), 111–127.MathSciNetCrossRef

Zhang, L., & Zhang, B. (2004). The quotient space theory of problem solving. Fundamenta Informaticae, 59(2-3), 287–298.MathSciNetMATH

Zhang, T., Ramakrishnan, R., & Livny, M. (1997). Birch: a new data clustering algorithm and its applications. Data Mining and Knowledge Discovery, 1 (2), 141–182.CrossRef

Title: IbLT: An effective granular computing framework for hierarchical community detection
Authors: Shun Fu
Guoyin Wang
Ji Xu
Shuyin Xia
Publication date: 16-09-2021
Publisher: Springer US
Published in: Journal of Intelligent Information Systems / Issue 1/2022
Print ISSN: 0925-9902
Electronic ISSN: 1573-7675
DOI: https://doi.org/10.1007/s10844-021-00668-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2022

User profiling and satisfaction inference in public information access services

Coarse-grained decomposition and fine-grained interaction for multi-hop question answering

Exploiting stance hierarchies for cost-sensitive stance detection of Web documents

Analysis of information cascading and propagation barriers across distinctive news events

Upper bounds for can-tree and FP-tree

An overview of machine learning techniques in constraint solving

Premium Partner