Browsing by Keyword "Community detection"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item Community detection in networks using bio-inspired optimization: Latest developments, new results and perspectives with a selection of recent meta-heuristics(2020-02) Osaba, Eneko; Del Ser, Javier; Camacho, David; Bilbao, Miren Nekane; Yang, Xin She; Quantum; IADetecting groups within a set of interconnected nodes is a widely addressed problem that can model a diversity of applications. Unfortunately, detecting the optimal partition of a network is a computationally demanding task, usually conducted by means of optimization methods. Among them, randomized search heuristics have been proven to be efficient approaches. This manuscript is devoted to providing an overview of community detection problems from the perspective of bio-inspired computation. To this end, we first review the recent history of this research area, placing emphasis on milestone studies contributed in the last five years. Next, we present an extensive experimental study to assess the performance of a selection of modern heuristics over weighted directed network instances. Specifically, we combine seven global search heuristics based on two different similarity metrics and eight heterogeneous search operators designed ad-hoc. We compare our methods with six different community detection techniques over a benchmark of 17 Lancichinetti–Fortunato–Radicchi network instances. Ranking statistics of the tested algorithms reveal that the proposed methods perform competitively, but the high variability of the rankings leads to the main conclusion: no clear winner can be declared. This finding aligns with community detection tools available in the literature that hinge on a sequential application of different algorithms in search for the best performing counterpart. We end our research by sharing our envisioned status of this area, for which we identify challenges and opportunities which should stimulate research efforts in years to come.Item Community detection in weighted directed networks using nature-inspired heuristics(Springer Verlag, 2018) Osaba, Eneko; Del Ser, Javier; Camacho, David; Galvez, Akemi; Iglesias, Andres; Fister, Iztok; Fister, Iztok; Camacho, David; Novais, Paulo; Tallón-Ballesteros, Antonio J.; Yin, Hujun; Quantum; IAFinding groups from a set of interconnected nodes is a recurrent paradigm in a variety of practical problems that can be modeled as a graph, as those emerging from Social Networks. However, finding an optimal partition of a graph is a computationally complex task, calling for the development of approximative heuristics. In this regard, the work presented in this paper tackles the optimal partitioning of graph instances whose connections among nodes are directed and weighted, a scenario significantly less addressed in the literature than their unweighted, undirected counterparts. To efficiently solve this problem, we design several heuristic solvers inspired by different processes and phenomena observed in Nature (namely, Water Cycle Algorithm, Firefly Algorithm, an Evolutionary Simulated Annealing and a Population based Variable Neighborhood Search), all resorting to a reformulated expression for the well-known modularity function to account for the direction and weight of edges within the graph. Extensive simulations are run over a set of synthetically generated graph instances, aimed at elucidating the comparative performance of the aforementioned solvers under different graph sizes and levels of intra- and inter-connectivity among node groups. We statistically verify that the approach relying on the Water Cycle Algorithm outperforms the rest of heuristic methods in terms of Normalized Mutual Information with respect to the true partition of the graph.Item Dynamic Partitioning of Evolving Graph Streams Using Nature-Inspired Heuristics(Springer Verlag, 2019) Osaba, Eneko; Bilbao, Miren Nekane; Iglesias, Andres; Del Ser, Javier; Galvez, Akemi; Fister, Iztok; Fister, Iztok; Rodrigues, João M.F.; Cardoso, Pedro J.S.; Monteiro, Jânio; Lam, Roberto; Krzhizhanovskaya, Valeria V.; Lees, Michael H.; Sloot, Peter M.A.; Dongarra, Jack J.; Quantum; IADetecting communities of interconnected nodes is a frequently addressed problem in situation that be modeled as a graph. A common practical example is this arising from Social Networks. Anyway, detecting an optimal partition in a network is an extremely complex and highly time-consuming task. This way, the development and application of meta-heuristic solvers emerges as a promising alternative for dealing with these problems. The research presented in this paper deals with the optimal partitioning of graph instances, in the special cases in which connections among nodes change dynamically along the time horizon. This specific case of networks is less addressed in the literature than its counterparts. For efficiently solving such problem, we have modeled and implements a set of meta-heuristic solvers, all of them inspired by different processes and phenomena observed in Nature. Concretely, considered approaches are Water Cycle Algorithm, Bat Algorithm, Firefly Algorithm and Particle Swarm Optimization. All these methods have been adapted for properly dealing with this discrete and dynamic problem, using a reformulated expression for the well-known modularity formula as fitness function. A thorough experimentation has been carried out over a set of 12 synthetically generated dynamic graph instances, with the main goal of concluding which of the aforementioned solvers is the most appropriate one to deal with this challenging problem. Statistical tests have been conducted with the obtained results for rigorously concluding the Bat Algorithm and Firefly Algorithm outperform the rest of methods in terms of Normalized Mutual Information with respect to the true partition of the graph.