User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Community detection in networks with positive and negative links.

Primary tabs

download
  • Open access
  • PDF
  • 621.28 K
Traag, Vincent [UCL] Bruggeman, Jeroen

Detecting communities in complex networks accurately is a prime challenge, preceding further analyses of network characteristics and dynamics. Until now, community detection took into account only positively valued links, while many actual networks also feature negative links. We extend an existing Potts model to incorporate negative links as well, resulting in a method similar to the clustering of signed graphs, as dealt with in social balance theory, but more general. To illustrate our method, we applied it to a network of international alliances and disputes. Using data from 1993-2001, it turns out that the world can be divided into six power blocs similar to Huntington's civilizations, with some notable exceptions.

Document type Article de périodique (Journal article) – Article de recherche – Journal Article, Research Support, Non-U.S. Gov't
Access type Accès libre
Publication date 2009
Language Anglais
Journal information "Physical review. E, Statistical, nonlinear, and soft matter physics" - Vol. 80, no. 3 Pt 2, p. 036115 (2009)
Peer reviewed yes
issn 1539-3755
e-issn 1550-2376
Publication status Publié
Affiliation UCL - FSA/INMA - Département d'ingénierie mathématique
MESH Subject Social Support ; Social Behavior ; Residence Characteristics ; Population Dynamics ; Models, Theoretical ; Feedback ; Computer Simulation
Links
  1. BOCCALETTI S, LATORA V, MORENO Y, CHAVEZ M, HWANG D, Complex networks: Structure and dynamics, 10.1016/j.physrep.2005.10.009
  2. Dorogovtsev S. N., Goltsev A. V., Mendes J. F. F., Critical phenomena in complex networks, 10.1103/revmodphys.80.1275
  3. J. Bruggeman, Social Networks: An Introduction (2008)
  4. Duch Jordi, Arenas Alex, Community detection in complex networks using extremal optimization, 10.1103/physreve.72.027104
  5. Palla Gergely, Derényi Imre, Farkas Illés, Vicsek Tamás, Uncovering the overlapping community structure of complex networks in nature and society, 10.1038/nature03607
  6. Newman M. E. J., Finding community structure in networks using the eigenvectors of matrices, 10.1103/physreve.74.036104
  7. Girvan M., Newman M. E. J., Community structure in social and biological networks, 10.1073/pnas.122653799
  8. Reichardt Jörg, Bornholdt Stefan, Statistical mechanics of community detection, 10.1103/physreve.74.016110
  9. Harary Frank, On the notion of balance of a signed graph., 10.1307/mmj/1028989917
  10. Fortunato S., Barthelemy M., Resolution limit in community detection, 10.1073/pnas.0605965104
  11. Kumpula J. M., Saramäki J., Kaski K., Kertész J., Limited resolution in complex network community detection with Potts model approach, 10.1140/epjb/e2007-00088-4
  12. F. Heider, J. Psychol., 21, 107 (1946)
  13. Davis James A., Clustering and Structural Balance in Graphs, 10.1177/001872676702000206
  14. D. Cartwright, Elemente der Mathematik, 23, 85 (1968)
  15. Doreian Patrick, Mrvar Andrej, A partitioning approach to structural balance, 10.1016/0378-8733(95)00259-6
  16. Jensen Pablo, Network-based predictions of retail store commercial categories and optimal locations, 10.1103/physreve.74.035101
  17. Newman M. E. J., Girvan M., Finding and evaluating community structure in networks, 10.1103/physreve.69.026113
  18. Leicht E. A., Newman M. E. J., Community Structure in Directed Networks, 10.1103/physrevlett.100.118703
  19. Gómez Sergio, Jensen Pablo, Arenas Alex, Analysis of community structure in networks of correlated data, 10.1103/physreve.80.016114
  20. J. Reichardt, Structure in Complex Networks (2008)
  21. Wu F. Y., The Potts model, 10.1103/revmodphys.54.235
  22. Blondel Vincent D, Guillaume Jean-Loup, Lambiotte Renaud, Lefebvre Etienne, Fast unfolding of communities in large networks, 10.1088/1742-5468/2008/10/p10008
  23. Guimera R., Mossa S., Turtschi A., Amaral L. A. N., The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles, 10.1073/pnas.0407994102
  24. Kirkpatrick S., Gelatt C. D., Vecchi M. P., Optimization by Simulated Annealing, 10.1126/science.220.4598.671
  25. Danon Leon, Díaz-Guilera Albert, Duch Jordi, Arenas Alex, Comparing community structure identification, 10.1088/1742-5468/2005/09/p09008
  26. Guimerà Roger, Nunes Amaral Luís A., Functional cartography of complex metabolic networks, 10.1038/nature03288
  27. Lancichinetti Andrea, Fortunato Santo, Radicchi Filippo, Benchmark graphs for testing community detection algorithms, 10.1103/physreve.78.046110
  28. Newman M. E. J., Modularity and community structure in networks, 10.1073/pnas.0601602103
  29. Ghosn Faten, Palmer Glenn, Bremer Stuart A., The MID3 Data Set, 1993—2001: Procedures, Coding Rules, and Description, 10.1080/07388940490463861
  30. Gibler Douglas M., Sarkees Meredith Reid, Measuring Alliances: the Correlates of War Formal Interstate Alliance Dataset, 1816–2000, 10.1177/0022343304041061
  31. S. P. Huntington, The Clash of Civilizations and the Remaking of World Order (1996)
  32. Hensel Paul R., Goertz Gary, Diehl Paul F., The Democratic Peace and Rivalries, 10.1111/0022-3816.00052
  33. Tocqueville Alexis de, Mansfield Harvey C., Winthrop Delba, Democracy in America, ISBN:9780226805368, 10.7208/chicago/9780226924564.001.0001
  34. H. Kissinger, Diplomacy (1994)
  35. Polachek Solomon W., Robst John, Chang Yuan-Ching, Liberalism and Interdependence: Extending the Trade-Conflict Model, 10.1177/0022343399036004002
  36. Henderson Errol A., Tucker Richard, Clear and Present Strangers: The Clash of Civilizations and International Conflict, 10.1111/0020-8833.00193
  37. Russett Bruce M., Oneal John R., Cox Michaelene, Clash of Civilizations, or Realism and Liberalism Déjà Vu? Some Evidence, 10.1177/0022343300037005003
  38. Flake G.W., Lawrence S., Giles C.L., Coetzee F.M., Self-organization and identification of Web communities, 10.1109/2.989932
  39. L. A. Adamic, LinkKDD ’05: Proceedings of the 3rd International Workshop on Link Discovery (2005)
Bibliographic reference Traag, Vincent ; Bruggeman, Jeroen. Community detection in networks with positive and negative links.. In: Physical review. E, Statistical, nonlinear, and soft matter physics, Vol. 80, no. 3 Pt 2, p. 036115 (2009)
Permanent URL http://hdl.handle.net/2078.1/28551