Abstract Community structure is one of the most prominent features of complex networks. Community structure detection is of great importance to provide insights into the network structure and functionalities. Most proposals focus on static networks. However, finding communities in a dynamic network is even more challenging, especially when communities overlap with each other. In this article, we present an online algorithm, called OLCPM, based on clique percolation and label propagation methods. OLCPM can detect overlapping communities and works on temporal networks with a fine granularity. By locally updating the community structure, OLCPM delivers significant improvement in running time compared with previous clique percolation techniques. The experimental results on both synthetic and real-world networks illustrate the effectiveness of the method.
Cazabet and Amblard @cite_28 proposed an online algorithm called iLCD. In this work, the dynamic network is considered as a sequence of events (adding or removing edges). iLCD is using a multi-agent system: each community is an agent on the network, which can integrate or reject nodes. The agents are bounded by a certain number of operating rules, like updating existing communities, creating new communities or merging similar ones. Communities can be updated at each apparition or deletion of links.
@cite_28
1978708265 2011211123 2744920931 2126679325
In this paper, we study the problem of reaching a consensus among all the agents in the networked control systems (NCS) in the presence of misbehaving agents. A reputation-based resilient distributed control algorithm is first proposed for the leader-follower consensus network. The proposed algorithm embeds a resilience mechanism that includes four phases (detection, mitigation, identification, and update), into the control process in a distributed manner. At each phase, every agent only uses local and one-hop neighbors' information to identify and isolate the misbehaving agents, and even compensate their effect on the system. We then extend the proposed algorithm to the leaderless consensus network by introducing and adding two recovery schemes (rollback and excitation recovery) into the current framework to guarantee the accurate convergence of the well-behaving agents in NCS. The effectiveness of the proposed method is demonstrated through case studies in multirobot formation control and wireless sensor networks. Leader-driven community detection algorithms (LdCD hereafter) constitute a new trend in devising algorithms for community detection in large-scale complex networks. The basic idea is to identify some particular nodes in the target network, called leader nodes, around which local communities can be computed. Being based on local computations, they are particularly attractive to handle large-scale networks. In this paper, we describe a framework for implementing LdCD algorithms, called LICOD. We propose also a new way for evaluating performances of community detection algorithms. This consists on transforming data clustering problems into a community detection problems. External criteria for evaluating obtained clusters can then be used for comparing performances of different community detection approaches. Results we obtain show that our approach outperforms top state of the art algorithms for community detection in complex networks. In this paper, a novel decentralized task allocation algorithm based on the Hungarian approach is proposed. The proposed algorithm guarantees an optimal solution as long as the agent network is connected, i.e., the second smallest eigenvalue of the Laplacian matrix of the agent graph is greater than zero. In order to show the motivation of the proposed algorithm, the original centralized auction and Hungarian algorithms are compared in terms of the converging speed versus the number of agents. The result shows the superiority of the Hungarian algorithm in scalability over the auction algorithm. Then, the performance of the proposed decentralized Hungarian-Based algorithm (DHBA) is compared with the consensus-based auction algorithm (CBAA) under different situations, including different number of agents and different network topologies. The simulation results show that DHBA outperforms CBAA in all cases on the basis of the converging speed, the optimality of assignments, and the computational time. Community detection in social networks is a well-known problem encountered in many fields. Many traditional algorithms have been proposed to solve it, with recurrent problems: impossibility to deal with dynamic networks, sensitivity to noise, no detection of overlapping communities, exponential running time. This paper proposes a multi-agent system that replays the evolution of a network and, in the same time, reproduces the rise and fall of communities. After presenting the strengths and weaknesses of existing community detection algorithms, we describe the multi-agent system we propose. Then, we compare our solution with existing works, and show some advantages of our method, in particular the possibility to dynamically detect the communities.