One way of characterizing the topological and structural properties of vertices and edges in a graph is by using structural similarity measures. Measures like Cosine, Jaccard and Dice compute the similarities restricted to the immediate neighborhood of the vertices, bypassing important structural properties beyond the locality. Others measures, such as the generalized edge clustering coefficient, go beyond the locality but with high computational complexity, making them impractical in large-scale scenarios. In this paper we propose a novel similarity measure that determines the structural similarity by dynamically diffusing and capturing information beyond the locality. This new similarity is modeled as an iterated function that can be solved by fixed point iteration in super-linear time and memory complexity, so it is able to analyze large-scale graphs. In order to show the advantages of the proposed similarity in the community detection task, we replace the local structural similarity used in the SCAN algorithm with the proposed similarity measure, improving the quality of the detected community structure and also reducing the sensitivity to the parameter @math of the SCAN algorithm.
An algorithm to compute structural similarity based on distance dynamics have been proposed in @cite_24 . They propose a fast algorithm to detect high-quality community structure by merging nodes with high structural similarity. The structural similarity is defined as the result of three interaction patterns that dynamically change the similarity through the time. These interaction patterns are solved by fixed point iteration. Although the system presents dynamic behavior, they force its convergence by truncating similarities above one, and below zero.
@cite_24
2127225292
How can we uncover the natural communities in a real network that allows insight into its underlying structure and also potential functions? In this paper, we introduce a new community detection algorithm, called Attractor, which automatically spots the communities or groups in a network over time via local dynamic interaction. The basic idea is to envision a network as a dynamical system, and each agent interacts with its local partners. Instead of investigating the node dynamics, we actually examine the change of "distances" among linked nodes. As time evolves, these distances will be shrunk or stretched gradually based on their topological structures. Finally all distances among linked nodes will converge into a stable pattern, and communities can be intuitively identified. Thanks to the dynamic viewpoint of community detection, Attractor has several potential attractive properties: (a) Attractor provides an intuitive solution to analyze the community structure of a network, and faithfully captures the natural communities (with high quality). (b) Owing to its time complexity @math , Attractor allows finding communities on large networks. (c) The small communities or anomalies, usually existing in real-world networks, can be well pinpointed. (d) Attractor is easy to parameterize, since there is no need to specify the number of clusters. Extensive experiments on synthetic and real-world networks further demonstrate the effectiveness and efficiency of the proposed approach.