FlowPro

Local Community Detection via a Flow Propagation (FlowPro) method

Introduction

We propose a flow propagation algorithm (FlowPro) that finds the community of a node in a complex network without the knowledge of the entire graph. The novelty of the proposed approach is the fact that FlowPro is local and it does not require the knowledge of the entire graph as most of the existing methods from literature. This makes possible the application of FlowPro in extremely large graphs or in cases where the entire graph is unknown like in most social networks.

FlowPro is able to solve the single community detection problem without the knowledge of the entire graph structure. So, it simply compute the community of exactly one node, that is the major issue in most social network based applications.

The experimental results and comparisons to existing methods on real and synthetic data sets demonstrate the high performance and robustness of the proposed scheme.

Methodology

Figure 1. An example of the variation of the (a) stored flow and T (s) (b) and the acc during execution of the main process of FlowPro [3].

Figure 2. The quantity S(x) (stored flow of a node) and the local(x)/degree(x) for a synthetic graph using blue and red colors for the nodes that

belong on the community and does not belong on community, respectively [3].

In each iteration of the main process of FlowPro, the initial node propagates a flow that is shared to its neighbors. Each node is able to store, propagate to its neighbors and return a part of flow to the initial node.
When the algorithm converges, the stored flow of the nodes that belong on the community of initial node is generally higher than the stored flow of the rest graph nodes resulting the requested community.
In addition, using the stored flow of the nodes, FlowPro is able to extend the neighbors of initial node decreasing shortest paths between the nodes that belong on the community and to remove the neighbors of initial node, subtracting bridges of the community.

Figure 3. The evolution of FlowPro community detection result (before the black line) in a synthetic graph [3].

Figure 4. An example of visualization results of CoViFlowPro method on a real graph [2].

Downloads

Matlab code of FlowPro algorithm and the synthetic datasets used in [1-3]. See readme.txt files for instructions. You can use them only for non-commercial purposes. If you use them, please cite the papers [1-3].
Powerpoint presentation of FlowPro [1].

Related Publications

[1]. C. Panagiotakis, H. Papadakis and P. Fragopoulou, FlowPro: A Flow Propagation Method for Single Community Detection, IEEE Consumer Communications and Networking Conference, 2014.

[2] C. Panagiotakis, H. Papadakis and P. Fragopoulou, CoViFlowPro: A Community Visualization method based on a Flow Propagation Algorithm, International Conference on Bio-inspired Information and Communications Technologies (formerly BIONETICS) - BICT 2014, 2014.

[3]. C. Panagiotakis, H. Papadakis and P. Fragopoulou, Local Community Detection via Flow Propagation, International conference on Advances in Social Network Analysis and Mining (ASONAM), 2015 (under review).

Acknowledgments: This work is partially supported by the “ARCHIMEDE III: Education and Lifelong Learning” (Project’s Acronym: P2PCOORD) project.