Overlapping community discovering method based on spectral clustering and fuzzy sets

Abstract

The invention relates to an overlapping community discovering method based on spectral clustering and fuzzy sets. The overlapping community discovering method comprises the steps that 1, data sets ofa social network are read to generate a network structure graph, and the attribute information of nodes in the network is acquired; 2, the Jaccard coefficient and the attribute information of the nodes in the network are combined to calculate the similarity value among the nodes in the network; 3, a similarity matrix is built based on the similarity value among the nodes, and accordingly the normalized Laplacian matrix is built; 4, the feature vector and the feature value of each node are calculated, and a new feature vector is generated by utilizing methods of iteration and compression; 5, the new feature vector is orthogonalized, the membership grade is calculated, and the nodes with a plurality of high community membership grade values are subjected to division of overlapping communities; 6, the community division meeting the highest modularity requirement is selected according to the modularity divided each time; and 7, the final community division result is output. The overlappingcommunity discovering method can efficiently and accurately discover and divide the overlapping structures in the complex network.

Description

technical field [0001] The invention relates to the technical field of overlapping community discovery on complex networks, in particular to an overlapping community discovery method based on spectral clustering and fuzzy sets. Background technique [0002] With the rapid development of Internet information interaction, a variety of complex network structures have emerged, such as social networks, scientists' cooperation networks, food chain networks, and metabolic networks. In a social network, each node represents an individual in the network, while an edge represents a connection between individuals, and the attribute value of an edge represents a more specific connection between individuals. The community structure in social networks usually shows that the nodes within the community are closely connected, while the nodes between communities are sparsely connected. Community discovery is one of the key techniques for studying complex network structures. At present, the ...

AI Technical Summary

Problems solved by technology

Although these algorithms can discover the network community structure well, they can only discover the network community structure in the convex spherical sample space, and cannot discover community structures of various shapes. At the same time, they are easy to fall into the dilemma of local optimal solutions. Spectral clustering in graph theory is applied to community discovery, and a community discovery algorithm based on spectral clustering is proposed

[0004] At present, many scholars have conducted research on community discovery based on spectral clustering, and have achieved some results, but there are still several problems: First, the time and space complexity of the algorithm is relatively high compared to other types of algorithms, and it is difficult to deal with large-scale There are deficiencies in the network; secondly, the algorithm cannot find overlapping community structures; finally, the selection of parameters in the process of community division is not stable, resulting in low accuracy of community discovery

Images