Block diagonal dominance-based dynamic programming for detecting community
- PDF / 1,549,303 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 64 Downloads / 190 Views
Block diagonal dominance‑based dynamic programming for detecting community Xingquan Li1 · Cong Cao2 · Tao Zhang3
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Clustering or partition is a fundamental work for graph or network. Detecting communities is a typical clustering, which divides a network into several parts according to the modularity. Community detection is a critical challenge for designing scalable, adaptive and survivable trust management protocol for a community of interestbased social IoT system. Most of the existed methods on community detection suffer from a common issue that the number of communities should be prior decided. This urges us to estimate the number of communities from the data by some way. This paper concurrently considers eliminating the number of communities and detecting communities based on block diagonal dominace adjacency matrix. To construct a block diagonal dominance adjacency matrix for the input network, it first reorders the node number by the breadth-first search algorithm. For the block diagonal dominance adjacency matrix, this paper shows that the numbers of nodes in a community should be continuous adjacent. And thus, it only needs insert some breakpoints in node number sequence to decide the number of communities and the nodes in every community. In addition, a dynamic programming algorithm is designed to achieve an optimal community detection result. Experimental results on a number of realworld networks show the effectiveness of the dynamic programming approach on the community detection problem. Keywords Social IoT system · Community of interest network · Block diagonal dominance matrix · Dynamic programming · Deep graph neural network
* Xingquan Li [email protected] 1
School of Mathematics and Statistics, Minnan Normal University, Zhangzhou, China
2
Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou, China
3
Laboratory of Urban Land Resources Monitoring and Simulation, Ministry of Land and Resources, Shenzhen, China
13
Vol.:(0123456789)
X. Li et al.
1 Introduction A future physical world is connected into cyberspace by the Internet of Things (IoT) system [1]. The main function of IoT technology is collecting and sharing information, and which is achieved via a trust management protocol for managing trust between IoT entities. A trust management protocol for IoT must be resilient to trustrelated attacks to survive. However, existed trust management model does not pay attention to the social relationship among entities, which is important in social IoT systems. Designing and evaluating a scalable, adaptive and survivable trust management protocol for a community of interest (CoI)-based social IoT system is seriously important [2, 33]. For a CoI-based social IoT environment, nodes form into communities of interest (Fig. 1) and each node has a unique address to identify. Two nodes belonging to the same CoI have specific social interests and strong social ties, which could be ma
Data Loading...
