/Community-Detection-Based-On-Seed-Node

Primary LanguageJupyter Notebook

Abstract

From Earlier days Community detection is one of the most popular topic and is an important structure in social network. Community detection is required to define that who is belong to which community. Further numerous approaches are already proposed for finding community over a social network. In this paper we will propose a new approach of community detection based on seed centric approach in which we will discuss that how we are finding the seed node. We will also discuss about how seed set is expanding from remaining nodes which do not belongs to any community directly. The basic idea underlying in this approach is to identifying special nodes in the target network, called seed so that we can detect good community. Different algorithms adopt different approaches of seed selection definitions and seed set expansion definitions for communities construction. We will apply our algorithm in three classical data sets and will compare to other algorithms.

Dataset

Network name
#node
#edge
Refrences
Karated Club3478[2]
Dolphins Network62159[3]
Political Books105441[4]

Setup

important library.

  • networkx
  • collections
  • math
  • matplotlib

    • Experimental Result.

    Network name
    #node
    #edge
    #Community
    Modularity
    Refrences
    Karated Club347820.371[2]
    Dolphins Network6215950.505[3]
    Political Books10544140.524[4]

    alt text

    alt text

    alt text

    Comparision between some popular existed community detection algorithm and our algorithm.

    Name of Network
    Algorithms
    Communities
    Modularity
    Karate ClubNewman[1] 50.40
    Lovain[5] 40.41
    Walktrap[6] 50.35
    Licod[7] 30.24
    Yasca[8] 20.34
    Our Algorithm20.37
    Dolphins NetworkNewman 50.51
    Lovain 40.52
    Walktrap 40.50
    Licod 60.42
    Yasca 30.24
    Our Algorithm40.52
    Political BooksNewman50.52
    Lovain 50.51
    Walktrap 40.51
    Licod 20.48
    Yasca 30.35
    Our Algorithm50.50

    Visual Comparision based on Modularity.

    Refrences.

    [1] Girvan, M., Newman, M.E.J.: Community structure in social and biological net- works. PNAS 99(12), 7821–7826 (2002)

    [2] Zachary, W.W.: An information flow model for conflict and fission in small groups.Journal of Anthropological Resea33, 452–473 (1977)

    [3] Lusseau, D., Schneider, K., Boisseau, O.J., Haase, P., Slooten, E., Dawson, S.M.:The bottlenose dolphin community of doubtful sound features a large proportion of long- lasting associations. Behavioral Ecology and Sociobiology 54, 396–405 (2003)

    [4] Krebs, V.: Political books network, http://www.orgnet.com/
    [5]] Blondel, V.D., Guillaume, J.I., Lefebvre, E.: Fast unfolding of communities in large networks, pp. 1–12 (2008)
    [6] Pons, P., Latapy, M.: Computing communities in large networks using random walks. J. Graph Algorithms Appl. 10(2), 191–218 (2006)
    [7] Kanawati, R.: Licod: Leaders identification for community detection in complex networks. In: SocialCom/PASSAT, pp. 577–582 (2011)
    [8] Kanawati, R.: Yasca: A collective intelligence approach for community detection in complex networks. CoRR abs/1401.4472 (2014)