Derivatives in Graph Space with Applications for Finding and Tracking Local Communities

Community detection in networks has gained a lot of attention especially after emergence of online social networks. Community detection methods in networks can be classified into two domains: global methods and local methods. Global methods need the whole information of the network, whereas the local ones need information of a certain area of the network where they want to discover communities. Real-world social networks are typically very large, making the global community detection methods impractical due to the computation expenses. Therefore, local community detection algorithms, which are requiring less computation and space, have met with renewed interest. In this research two derivative-based methods for finding and tracking local communities are proposed. Mapping the concepts of derivatives into graph space in a practical manner poses few challenges. For instance, in Euclidean space, every point has three dimensions, whereas in graph space the dimension (or degree) of every node can be different. Firstly, we propose a general framework for finding derivatives in graph space. This mentioned framework enables us to bring derivative-based methods into graph theory. Secondly, inspired by the active contour algorithm in computer vision domain, we propose a local derivative-based community detection method. The proposed method is built upon concepts of curvature and gradient of the community’s boundary. Curvature and gradient comprise a velocity function to determine whether the boundary should expand to include a candidate node in its vicinity. Finally, based on derivative-based concept of surface tension in chemistry, we propose a model for tracking local communities in dynamic networks where new nodes/edges are added in a stream of atomic changes. The binding forces between the molecules of the same liquid substance give them shape with the minimum surface tension. That is to say, if molecules of the same substance are added to the community, the surface tension should not increase. In the network context, if a node can be added to a community it reduces the surface tension of the community. Experimental results validate the superiority of the proposed methods.