http://iet.metastore.ingenta.com
1887

Detection of local community structures in complex dynamic networks with random walks

Detection of local community structures in complex dynamic networks with random walks

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Systems Biology — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Identification of interaction patterns in complex networks via community structures has gathered a lot of attention in recent research studies. Local community structures provide a better measure to understand and visualise the nature of interaction when the global knowledge of networks is unknown. Recent research on local community structures, however, lacks the feature to adjust itself in the dynamic networks and heavily depends on the source vertex position. In this study the authors propose a novel approach to identify local communities based on iterative agglomeration and local optimisation. The proposed solution has two significant improvements: (i) in each iteration, agglomeration strengthens the local community measure by selecting the best possible set of vertices, and (ii) the proposed vertex and community rank criterion are suitable for the dynamic networks where the interactions among vertices may change over time. In order to evaluate the proposed algorithm, extensive experiments and benchmarking on computer generated networks as well as real-world social and biological networks have been conducted. The experiment results reflect that the proposed algorithm can identify local communities, irrespective of the source vertex position, with more than 92% accuracy in the synthetic as well as in the real-world networks.

References

    1. 1)
      • P. Gloor , R. Laubacher , S. Oynes , Y. Zhao . Visualization of interaction patterns in collaborative knowledge networks for medical applications. Proc. HCII, Crete, Greece
    2. 2)
      • S. Fortunato , V. Latora , M. Marchiori . Method to find community structures based on information centrality. Phy. Rev. E , 5
    3. 3)
      • M. Girvan , M.E.J. Newman . Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA
    4. 4)
      • S. Cho , S.G. Park , d.o.H. Lee , B.C. Park . Protein-protein interaction networks: from interactions to networks. J. Biochem. Mol. Biol. , 1 , 45 - 52
    5. 5)
      • J.A. Dunne , R.J. Williams , N.D. Martinez . Food-web structure and network theory: the role of connectance and size. Proc. Natl. Acad. Sci. , 20 , 12917 - 12922
    6. 6)
      • S. Wasserman , K. Faust . (1994) Social network analysis.
    7. 7)
      • A. Pothen , H.D. Simon , K.-P. Liou . Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. , 3 , 430 - 452
    8. 8)
      • M. Fiedler . Albegraic connectivity of graphs. Czech. Math J. , 298 - 305
    9. 9)
      • B.W. Kernighan , S. Lin . An efficient heuristic procedure for partitioning graph. Bell Syst. Tech. J. , 291 - 307
    10. 10)
      • J. Travers , S. Milgram . An experimental study of the small world problem. Sociometry , 4 , 425 - 443
    11. 11)
      • W.Y.C. Chen , A.W.M. Dress , W.Q. Yu . Checking the reliability of a new approach towards detecting community structures in networks using linear programming. IET Syst. Biol. , 5 , 286 - 291
    12. 12)
      • A. Clauset . Finding local community structure in networks. Phys. Rev. E
    13. 13)
      • R.B. Almeida , V.A.F. Almeida . Local community identification through user access patterns. Clin. Orthopaedics Relat. Res.
    14. 14)
      • V.C. Barbosa , R. Donangelo , S.R. Souza . Emergence of scale-free networks from local connectivity and communication trade-offs. Phys. Rev. E
    15. 15)
      • V. Farutin , K. Robison , E. Lightcap . Edge-count probabilities for the identification of local protein communities and their organization. Proteins , 3 , 800 - 818
    16. 16)
      • G. Palla , I. Derenyi , I. Farkas , T. Vicsek . Uncovering the overlapping community structure of complex networks in nature and society. Nature
    17. 17)
      • V. Spirin , L.A. Mirny . Protein complexes and functional modules in molecular networks. Proc. Natl. Acad. Sci. USA , 21 , 12123 - 12128
    18. 18)
      • J.P. Bagrow , E.M. Bollt . Local method for detecting communities. Phys. Rev. E (Stat. Nonlinear Soft Matter Phys.) , 4
    19. 19)
      • D.J. de Solla Price . Networks of Scientific Papers. Science , 510 - 515
    20. 20)
      • T. Ito , T. Chiba , R. Ozawa , M. Yoshida , M. Hattori , Y. Sakaki . A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proc. Natl. Acad. Sci. USA , 8 , 4569 - 4574
    21. 21)
      • J.M. Kleinberg , R. Kumar , P. Raghavan , S. Rajagopalan , A.S. Tomkins . The Web as a graph: Measurements, models and methods. Lect. Notes Comput. Sci. , 1 - 17
    22. 22)
      • Fouss, F., Pirotte, A., Saerens, M.: `A novel way of computing similarities between nodes of a graph, with application to collaborative recommendation', Proc. 2005 IEEE/WIC/ACM Int. Conf. Web Intelligence, WI ‘05:, 2005, p. 550–556.
    23. 23)
      • D. Aldous , J.A. Fill . (2002) Reversible Markov chains and random walks on graphs–chapter 9: a second look at general Markov chains.
    24. 24)
      • L. Lovsz . (1993) Combinatorics, Paul Erdos is eighty.
    25. 25)
      • M. Latapy , P. Pons . (2004) Computing communities in large networks using random walks.
    26. 26)
      • M.R. Garey , D.S. Johnson . (1997) Computers and intractability: a guide to the theory of NP-completeness, (series of books in the mathematical sciences).
    27. 27)
      • M.E.J. Newman , M. Girvan . Finding and evaluating community structure in networks. Phys. Rev. E
    28. 28)
      • J.P. Bagrow . Evaluating local community methods in networks. J. Stat. Mech.: Theory Exp. , 5
    29. 29)
      • L. Danon , A. Díaz-Guilera , J. Duch , A. Arenas . Comparing community structure identification. J. Stat. Mech.: Theory Exp. , 9
    30. 30)
      • A.L. Fred , A.K. Jain . Robust data clustering. Comp. Vis. Pattern Recognit., IEEE Comp. Soc.
    31. 31)
      • A. Strehl , J. Ghosh . Cluster ensembles – a knowledge reuse framework for combining multiple partitions. J. Mac. Lear. Res. , 583 - 617
    32. 32)
      • A.J. Pocklington , J.D. Armstrong , S.G.N. Grant . Organization of brain complexity–synapse proteome form and function. Brief Funct. Genomic. Proteomic. , 1 , 66 - 73
    33. 33)
      • W.W. Zachary . An information flow model for conflict and fission in small groups. J. Anthropol. Res. , 452 - 473
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-syb.2007.0061
Loading

Related content

content/journals/10.1049/iet-syb.2007.0061
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address