A fine-grained loop-level parallel approach to efficient fuzzy community detection in complex networks

被引:0
作者
Munoz-Caro, Camelia [1 ]
Nino, Alfonso [1 ]
Reyes, Sebastian [1 ]
机构
[1] Univ Castilla La Mancha, Escuela Super Informat, Paseo Univ 4, Ciudad Real 13004, Spain
关键词
complex networks; fuzzy communities; machine learning; parallel algorithms; performance model; MODEL;
D O I
10.1002/cpe.5537
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Determining the inner organizational structure of sets of networked elements is of paramount importance to analyze real-world systems such as social, biological, or economic networks. To such an end, it is necessary to identify communities of interrelated nodes within the networks. Recently, a fuzzy community detection approach based on the minimization of a topological error functional has been proposed in the form of a gradient-based algorithm design pattern. However, the intrinsic quadratic algorithmic complexity of the procedure limits the problem size that can be efficiently treated. Here, we extend the ability of this approach to analyze larger networks resorting to parallelism. Thus, we identify the concurrency sources in the gradient-based algorithm design pattern. To determine the parallelization limits, we develop a two-dimensional performance model as a function of the number of processors and network size. The model permits to compute the maximum possible speedup. Another model is presented to find the maximum problem size tractable in a given amount of time. Application of the previous models to a set of benchmark networks shows that parallelization enhances the proposed fuzzy community detection approach in more than an order of magnitude. This allows treatment of networks with several hundred thousand nodes in a time frame of hours.
引用
收藏
页数:16
相关论文
共 57 条
[1]  
Amdahl GM, 1967, P AM FED INF PROC SO
[2]  
Anderson R, 1984, STANG841003 STANF U, P18
[3]  
[Anonymous], 2016, Network Science
[4]  
[Anonymous], 2009, Introduction to Algorithms
[5]  
[Anonymous], 2018, SURF VERS 15
[6]   The Architecture of complexity [J].
Barabasi, Albert-Lashlo .
IEEE CONTROL SYSTEMS MAGAZINE, 2007, 27 (04) :33-42
[7]  
Bezdek J. C., 1981, Pattern recognition with fuzzy objective function algorithms
[8]   PFCA: An influence-based parallel fuzzy clustering algorithm for large complex networks [J].
Bhatia, Vandana ;
Rani, Rinkle .
EXPERT SYSTEMS, 2018, 35 (06)
[9]   DFuzzy: a deep learning-based fuzzy clustering model for large graphs [J].
Bhatia, Vandana ;
Rani, Rinkle .
KNOWLEDGE AND INFORMATION SYSTEMS, 2018, 57 (01) :159-181
[10]   Fuzzy clustering in community detection based on nonnegative matrix factorization with two novel evaluation criteria [J].
Binesh, Neda ;
Rezghi, Mansoor .
APPLIED SOFT COMPUTING, 2018, 69 :689-703