Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2018 May 7;13(5):e0196447.
doi: 10.1371/journal.pone.0196447. eCollection 2018.

Micro-blog user community discovery using generalized SimRank edge weighting method

Jinshan Qi  1   2 , Xun Liang  1 , Xiaoping Zhou  1 , Zhiyu Li  1 , Yu Liu  1 , Hengchao Cheng  1
Affiliations

Micro-blog user community discovery using generalized SimRank edge weighting method

Jinshan Qi et al. PLoS One. .

Erratum in

Abstract

Community discovery is one of the most popular issues in analyzing and understanding a network. Previous research suggests that the discovery can be enhanced by assigning weights to the edges of the network. This paper proposes a novel edge weighting method, which balances both local and global weighting based on the idea of shared neighbor ranging between users and the interpersonal significance of the social network community. We assume that users belonging to the same community have similar relationship network structures. By controlling the measure of "neighborhood", this method can adequately adapt to real-world networks. Therefore, the famous similarity calculation method-SimRank-can be regarded as a special case of our method. According to the practical significance of social networks, we propose a new evaluation method that uses the communication rate to measure its divided demerit to better express users' interaction relations than the ordinary modularity Q. Furthermore, the fast Newman algorithm is extended to weighted networks. In addition, we use four real networks in the largest Chinese micro-blog website Sina. The results of experiments demonstrate that the proposed method easily meets the balancing requirements and is more robust to different kinds of networks. The experimental results also indicate that the proposed algorithm outperforms several conventional weighting methods.

PubMed Disclaimer

Conflict of interest statement

Competing Interests: The authors have declared that no competing interests exist.

Figures

Fig 1
Fig 1. Examples of local weighting schemes: (a1) clique with 3 nodes, (a2) clique with 4 nodes, (a3), (a4) graphs with no triangles.
In other words, no two nodes have common neighbors.
Fig 2
Fig 2. A network with 11 nodes.
Different colors represent different clusters.
Fig 3
Fig 3. A reduced example of a real social network.
Fig 4
Fig 4. Users b and d don’t have a direct connection, in contrast to Fig 3.
Fig 5
Fig 5. Micro-blog network structures of the four datasets.
Fig 6
Fig 6. Degree distributions of micro-blog networks of the four datasets.
Fig 7
Fig 7. The convergence rates of algorithms using Fig 3.
Fig 8
Fig 8. Similarity matrices calculated by RNRM and RNRM ++ using two different edge weighting methods.
Fig 9
Fig 9. Illustrations of the detection results with different algorithms for dataset Sina-Data1.
(a1) the fast Newman algorithm, (a2) FNAS, (a3) FNRNRM, (a4) FNRNRM++.
See this image and copyright information in PMC

References

    1. Agarwal G, Kempe D. Modularity-maximizing graph communities via mathematical programming. The European Physical Journal B. 2008; 66(3):409–418.
    1. Li HJ, Nie ZQ, Lee WC, Giles L, Wen JR. Scalable community discovery on textual data with relations. ACM Conference on Information and Knowledge Management. 2008; 1203–1212.
    1. Ferrara E. Community structure discovery in Facebook. International Journal of Social Network Mining. 2012; 1(1):67–90.
    1. Newman ME. Finding community structure in networks using the eigenvectors of matrices. Physical Review E Statistical Nonlinear & Soft Matter Physics. 2006; 74(3):036104. - PubMed
    1. Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America. 2004; 101(9):2658–2663. doi: 10.1073/pnas.0400054101 - DOI - PMC - PubMed

Publication types