Summary 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.

The present work addresses the problem of community detection in social networks. Determination of the community structure permits to identify the organizational and functional units of the network. To such an end, the most powerful approach is the fuzzy one. Here, each network node participates in all the communities simultaneously. In this paper, we develop a general formalism for fuzzy community detection in weighted, unweighted, directed and undirected social networks. Using an error functional measuring the difference between the predicted and observed network topologies, the problem is transformed into an unconstrained minimization. This allows to define a general algorithmic pattern based on the greedy paradigm, which can be customized to several different fuzzy community detection algorithms. Analysis of the algorithmic complexity of the procedure permits to determine the factors responsible for the variation of its running time. Using this information, we define an efficient algorithm (TRIBUNE) by applying a conjugate gradient approach. To determine the performance of TRIBUNE, we introduce a new network model specially designed as a fuzzy community detection benchmark. Using this benchmark, we show that TRIBUNE greatly reduces the dependence on the number of iterations of the optimization procedure. As a result, TRIBUNE needs in average 84% less time than the steepest descent baseline to solve a test set of benchmark networks. Furthermore, the performance of TRIBUNE increases with the network size.

In this work, we present a survey of the different parallel programming models and tools available today with special consideration to their suitability for high-performance computing. Thus, we review the shared and distributed memory approaches, as well as the current heterogeneous parallel programming model. In addition, we analyze how the partitioned global address space (PGAS) and hybrid parallel programming models are used to combine the advantages of shared and distributed memory systems. The work is completed by considering languages with specific parallel support and the distributed programming paradigm. In all cases, we present characteristics, strengths, and weaknesses. The study shows that the availability of multi-core CPUs has given new impulse to the shared memory parallel programming approach. In addition, we find that hybrid parallel programming is the current way of harnessing the capabilities of computer clusters with multi-core nodes. On the other hand, heterogeneous programming is found to be an increasingly popular paradigm, as a consequence of the availability of multi-core CPUs+GPUs systems. The use of open industry standards like OpenMP, MPI, or OpenCL, as opposed to proprietary solutions, seems to be the way to uniformize and extend the use of parallel programming models.

Abstract This work focuses on the use of computational Grids for processing the large set of jobs arising in parameter sweep applications. In particular, we tackle the mapping of molecular potential energy hypersurfaces. For computationally intensive parameter sweep problems, performance models are developed to compare the parallel computation in a multiprocessor system with the computation on an Internet‐based Grid of computers. We find that the relative performance of the Grid approach increases with the number of processors, being independent of the number of jobs. The experimental data, obtained using electronic structure calculations, fit the proposed performance expressions accurately. To automate the mapping of potential energy hypersurfaces, an application based on GRID superscalar is developed. It is tested on the prototypical case of the internal dynamics of acetone. Copyright © 2006 John Wiley & Sons, Ltd.

Scheduling algorithms play an important role in heterogeneous computing systems. Development of new scheduling strategies is an active research field. In this context, we present a general formulation of the self-scheduling problem, deriving a new, quadratic, self-scheduling algorithm. Initial tests comparing the performance of the new algorithm against well-established ones are carried out. Thus, working at the application level, we allocate sets of several thousand tasks in an Internet-based grid of computers that involves a transatlantic connection. In all the tests, the new algorithm performs better than the previous ones