Social communities in mobile phone communication networks Vincent Blondel University of Louvain (Belgium)

Social communities in mobile phone communication networks Vincent Blondel University of Louvain (Belgium) Aalto Complex Networks Factory June 2012

Communities

Belgian criminal network Belgian Federal Police (2006-2010 Database) 755 K people 1.400 K crimes Crimes: Time, type (out of 1300), location, etc Actors: Gender, age, nationality, etc

[Krings, Blondel, 2012]

55% drugs

78% intentional damage

[Krings, Blondel, 2012]

Social communities in mobile phone communication networks Vincent Blondel University of Louvain (Belgium)

! Community detection (Louvain method) ! Mobile phone communication networks ! Challenge

Communities

Physics Reports 486 (2010) 75–174

Contents lists available at ScienceDirect

Physics Reports journal homepage: www.elsevier.com/locate/physrep

Community detection in graphs Santo Fortunato ∗ Complex Networks and Systems Lagrange Laboratory, ISI Foundation, Viale S. Severo 65, 10133, Torino, I, Italy

article

info

Article history: Accepted 5 November 2009 Available online 4 December 2009 editor: I. Procaccia Keywords: Graphs Clusters Statistical physics

abstract The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks. © 2009 Elsevier B.V. All rights reserved.

Contents 1. 2. 3.

4.

5.

∗

Introduction............................................................................................................................................................................................. Communities in real-world networks ................................................................................................................................................... Elements of community detection......................................................................................................................................................... 3.1. Computational complexity ....................................................................................................................................................... 3.2. Communities ............................................................................................................................................................................. 3.2.1. Basics .......................................................................................................................................................................... 3.2.2. Local definitions ......................................................................................................................................................... 3.2.3. Global definitions....................................................................................................................................................... 3.2.4. Definitions based on vertex similarity ..................................................................................................................... 3.3. Partitions.................................................................................................................................................................................... 3.3.1. Basics .......................................................................................................................................................................... 3.3.2. Quality functions: Modularity................................................................................................................................... Traditional methods................................................................................................................................................................................ 4.1. Graph partitioning..................................................................................................................................................................... 4.2. Hierarchical clustering .............................................................................................................................................................. 4.3. Partitional clustering................................................................................................................................................................. 4.4. Spectral clustering..................................................................................................................................................................... Divisive algorithms ................................................................................................................................................................................. 5.1. The algorithm of Girvan and Newman .................................................................................................................................... 5.2. Other methods...........................................................................................................................................................................

Tel.: +39 011 6603090; fax: +39 011 6600049. E-mail address: [email protected].

0370-1573/$ – see front matter © 2009 Elsevier B.V. All rights reserved. doi:10.1016/j.physrep.2009.11.002

76 78 82 83 83 83 84 85 86 87 87 88 90 90 93 93 94 96 97 99

Louvain method

[Blondel, Guillaume, Lambiotte, Lefèvre Fast unfolding of communities in large networks, 2008]

Divide and Conquer: Partitioning Online Social Networks Josep M. Pujol, Vijay Erramilli, Pablo Rodriguez arXiv, 2010 Twitter: 2.4M/38M Mapping search relevance to social networks Jonathan Haynes, Igor Perisic Proceedings of the 3rd Workshop on Social Network Mining and Analysis, 2010 Linkedin, 21M Tracking the Evolution of Communities in Dynamic Social Networks Greene, D.; Doyle, D.; Cunningham, P.; International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 2010 Mobile phone, 4M/100M Real World Routing Using Virtual World Information Pan Hui, Sastry N. International Conference on Computational Science and Engineering, 2009 Flickr 1.8M/22M, LiveJournal 5.3M/77M, YouTube 1.1M/4.5M Community structure in audio clip sharing Gerard Roma, Perfecto Herrera International Conference on Intelligent Networking and Collaborative Systems, INCoS 2010 Freesound Subject clustering analysis based on ISI category classification Lin Zhang, Xinhai Liu, Frizo Janssens, Liming Liang and Wolfgang Glänzel Journal of Informetrics, Volume 4, Issue 2, April 2010 ISI 6M papers

?

Modularity Quality of a partition of a network in communities

[Newman, 2004]

Modularity Quality of a partition of a network in communities # edges in communities - expected # edges in communities total number of edges

[Newman, 2004]

Modularity Quality of a partition of a network in communities 3

4

3

5

3

5 4

3

3 6

# edges in communities - expected # edges in communities total number of edges 3

4 4

[Newman, 2004]


4

3

5

3

5 4

3

3 6


4 4

[Newman, 2004]


4

3

5

3

5 4

3

3 6


4 4

m edges, di degree of node i expected # edges between node i and node j = (di dj)/(2m)

[Newman, 2004]


4

3

5

3

5 4

3

3 6


4 4

m = 25, expect 0.3 edges m edges, di degree of node i expected # edges between node i and node j = (di dj)/(2m)

[Newman, 2004]


4

3

5

3

5 4

3 6


4

3

Expected 11.56

4 2.56

m nodes, di degree of node i expected # edges between node i and node j = (di dj)/(2m) expected # edges in community Sumi, j in C (di dj)/(2m)

[Newman, 2004]


4

3

5

3

5 4

3 6


4

3

Expected 11.56 Observed 15

4 2.56 6


[Newman, 2004]


4

3

5

3

5 4

3 6

4

3

Expected 11.56 Observed 15

4

# edges in communities - expected # edges in communities total number of edges 3 (15 + 6) - (11.56 + 2.56) = 0.275 25

2.56 6


[Newman, 2004]

0.275

? 0.32

0.383

Modularity [Newman, 2006] Resolution limit [Fortunato, Barthélemy, 2007] Optimizing modularity is NP-complete [Brandes, 2008] Louvain method (greedy method) [Blondel, Guillaume, Lambiotte, Lefèvre, 2008]

Louvain method Initially every node forms a community. For every node i, insert node i in a neighboring community that maximizes the resulting modularity gain. Repeat until a local maximum is attained. Construct the resulting network of communities and repeat the construction on the network of communities.

Louvain method Initially every node forms a community. For every node i, insert node i in a neighboring community that maximizes the resulting modularity. Repeat until a local maximum is attained. Construct the resulting network of communities and repeat the construction on the network of communities.

Hierarchy of communities Simple to implement Low computational complexity (not n2 but n log n). 118M nodes/1B links in 152mn



• Belgian phone call data – 6 months of communications – One Belgian main operator

• Network : – 2.6 M customers – 800M voice/text messages – location information (ZIP)

[Lambiotte, Blondel et al., 2008]

The heartbeat of Belgium

Distribution of calls received Number of customers

Number of calls received

Duration with distance

French

Dutch

∗

# ! ! ("

%

(b) ' # " "

' # "

'*

" ' ' '+ " ' " & '+

# (' $ # $ ( '*

«Gravitational of # " " ' " & ' + law» ( communication ' " # ! " ∗ ' # " & , [Krings, Calabrese, $ " Ratti, " Blondel, # ' 2008] " $ %& # ' & " ' ) % &' "

J. Stat. M

(a)

Frequency of calls

http://www.standaard.be/Artikel/PrintArtikel.aspx?artikelId=GVC3OHQ22

11/04/12 10:03

4 • TEN EERSTE

ZATERDAG 7 APRIL 2012 • DE MORGEN

Onderzoek telefoonverkeer verdeelt land in sociale regio’s die niet samenvallen met grenzen Opschudding rond

'België moet 17 provincies tellen' dinsdag 10 april 2012

België telt geen tien maar zeventien provincies

Onderzoeker brengt sociale netwerken binnen ons land in kaart

Huidige provinciegrenzen

Brugge

Antwerpen Gent Hasselt Brussel

Kuststreek en polders Zuid West-Vlaanderen Gent en Meetjesland Vlaamse Ardennen Waasland Antwerpen Brussel Dijleland en Hageland Kempen Limburg Ardennen Luik Oostkantons en Verviers Bergen en Borinage Namen Charleroi Doornik

Luik SAMEDI ET DIMANCHE 20 et 21 novembre 2010 / Edition Bruxelles / Quotidien / No 270 / EUR 1,50 / 02 225 55 55

Enquête sur les salaires Les avantages les plus demandés Le classement des salaires Qui n’est pas assez payé ?

*

100% techno Smartphones, applis, jeux : les musts

Mocht je ons land opdelen volgens onze sociale contacten, dan zou je aan zeventien regio’s komen. Dat blijkt uit onderzoek van de gerenommeerde professor Vincent Blondel (UCL), die ons telefoonverkeer in kaart bracht.

Pourquoi Johan Vande Lanotte peut réussir P. 2, 6 & 7 Je tweete, Comment donc je suis ? on devient L’influence réelle Le dico athlète du réseau social Twitter en Belgique Gaston olympique P. 34 à 37

P. 44

LOTTE BECKERS BRUSSEL

Officiële grenzen zijn vaak arbitrair, en een blik op onze sociale interacties lijkt die stellingtebevestigen.DattoontVincentBlondel, een mathematicus van de Université Catholique de Louvain die tot in de Verenigde Staten aanzien geniet. Op basis van meer dan 200 miljoentelefoongesprekken,datadiehijvaneenproviderheeftgekregen, ging hij na wie met wie belt,hoe lang en hoevaak.Debelangrijkstevraagdaarbijwas: waar zijn de bellers gevestigd? De conclusies zijn opmerkelijk. We mogendanweltienprovincieshebben,maar als je afgaat op onze sociale contacten, dan kom je uit bij zeventien sociale regio’s. Die tellenelk15tot66stedenendorpen.Deenige provincie die enige gelijkenis vertoont met haar sociale grenzen, is Limburg. WestVlaanderen daarentegen splitst zich sociologisch gezien in twee delen, de kust en de rest. Idem voor de provincie Antwerpen

P. 58 & 59

Bergen

(Antwerpen en Kempen) of OostVlaanderen, dat in zich drieën deelt. Voorbeelden genoeg ook van dorpen en gemeenten die zich op een andere provincie of regio richten dan diegene waar ze officieel toe behoren. Zo onderhouden Diestenaars meer contacten metLimburgers,terwijlGalmaardeneerder richting zuidelijk Oost-Vlaanderen lonkt. Brussel is, weinig verrassend, de grootste regio,en looptvan MeisetotGenappeen van

‘De verschillende sociale groepen

Volgens een uitgebreide studie op basis van ons telefoonverkeer zou ons land niet tien, maar wel bestaan altijd uit nabijgelegen dorpen zeventien provincies moeten tellen. en gemeenten’ lesoir.be

BON P. 33 LARGO WINCH 11,90 ¤

VINCENT BLONDEL UNIVERSITÉ CATHOLIQUE DE LOUVAIN

Namen

delen van het land bestond.” Wat nog opvalt, is het feit dat onze sociale regio’s op zichzelf lijken te staan,en weiniggelijkenissen vertoont met bestaande kaarten.Zowordtalgemeenaangenomen dat België 47 arbeidspolen kent, plekken waarheen Belgen trekken om te werken. Lennik Die verdelingkomt niet terug in de kaart van Blondel. Een tot Perwez. Wat Blondel zelf sociale regio kan ook perfect Aarlen meerdere steden tellen, zoals verbaasde, is dat we vooralbellennaarde mensen LeuvenenMechelenofHasselt en Genk. Aalst staat dan weer die dichtbij wonen en die we het vaakst zien.Wie in Oostendewoont, op zijn eentje. De enige bekende grens die bevestigd beltzeldenofnooitnaariemandinLimburg, wordt, is de taalgrens.Amper 2 procent van en omgekeerd.“We levenin een tijddat telefoontarievennietlangerafhankelijkzijnvan het intensieve telefoonverkeer is van noord naar zuid, of omgekeerd. de afstand en de meeste economische activiteitenlijkenminderafhankelijkvan transportkosten. Toch bestaan de verschillende sociale groepen altijd uit nabijgelegen dorOpinie >28 pen en gemeenten,terwijl het best mogelijk Jan Callebaut was dat één sociale regio uit verschillende

Onze sociale contacten beperken zich lang niet tot de provincie waarin we wonen. Integendeel, de bewoners van de tien huidige provincies hebben veel contact met Meurtre de mensen van aangrenzende Spanje dendert met rotvaart richting afgrond Politkovskaïa : 5 lasociété provincies. Dat blijkt uit een grootschalig onderzoek van Vincent professor aan de l’enquête Blondel, mène à Liège katholieke universiteit van Louvain-la-Neuve.

Philippe Moureaux annonce son départ

AYFER ERKUL BRUSSEL

Géographie / Une étude redessine la Belgique sur la base de la téléphonie mobile

L

’enquête sur l’assassinat brutal, en 2006, de la journaliste russe d’investigation Anna Politkovskaïa (probablement abattue par les réseaux de l’actuel pouvoir tchétchène favorable à Moscou) est relancée. Et elle mène les limiers russes jusqu’à… Liège, où ils se trouvent d’un milliard communicaen près ce moment pourde assister à tions ! J’aide confiance en ces l’exécution nouveaux de-résultats, ils sont robustes. Ils aux confirvoirs d’enquête demandés ment les données d’autres enquêautorités belges. tes similaires sur la Région bruxelEst-ce pour retrouver la traloise. Mais j’avoue avoir été ce de l’exécuteur matériel (pré-excitée ledu soirmeurtre, où j’ai puleréaliser sumé) Tché-cette carteRustam politiquement sensible évotchène Makhmudov, quant le lien des communes à faou s’agit-il d’interroger de cilités avec l’espace francophone. « nouveaux suspects » qui seVotre constat concernant raient apparus ces deux der- Bruxelles et sa périphérie est ponières années dans l’enquêintéressant. On ■ te ?litiquement pourrait « en tenir compte adminis! pour P.18l’organisation NOTRE DOSSIER trative et géopolitique de la Belgique », concluez-vous...

Les flux GSM élargissent Bruxelles

De Spaanse regering zegt geen beroep te zullen doen op het noodfonds. Toch blijft Europa zich grote zorgen maken over de Spaanse economie en de groeiende schuldencrisis in het land.

voor een opflakkeringvan de crisis nadat de rente van staatsobligatiesde hoogte in ging. Afgelopenweekbereiktehetrendementvan tienjarige staatsleningen de piek van 5,86 procent. Dat is het hoogste punt sinds vorig jaar begin december. Dinsdag verklaarde de minister van Economie Luis de Guindos dat de overheidsschuld in een jaar gestegen was van 63,4 naar 68,5 procent van het bruto binnenlands product (bbp). Dat is het hoogste peil sinds 1995. Tegen eind dit jaar zou die schuld nog verder oplopen tot bijna 80 procent en dat is meteen het hoogste peil ooit. De economischetoestand van het land is dramatisch, had premier Rajoy afgelopen week gezegd in tijdens een meeting van zijn Partio Popular. De werkloosheid is enorm. Meer dan 23 procent van de bevolking heeft geen werk. Van de Spaanse jongeren vindt maar liefst een op de twee geen baan. IntussenheeftdevastgoedmarktinSpanje zich nog lang niet hersteld van de klappen na de eurocrisis van 2008. Vorig jaar zakten de verkoop van woningen met meer dan 40 procent. Het ministerie van Binnenlandse Zaken berekende dat bijna 3,5 miljoen huizen leegstaan in het land. De crisis in de immobiliënsector volgde najarenvaneengrotebouwwoedeinSpanje. Die werd geleid door de gemakkelijke kre-

Blondel LE analyseerde half jaar lang BOURGMESTREeen de Molenbeek explique au «al Soirhet » telefoon- en sms-verkeer in ons land. Hij kreeg die qu’ilvan quitte een la présidence de la fédération bruxelloise du PS. bracht meer dan 800 miljoen communicaties van gegevens telefoonprovider. Blondel ongeveer A drie miljoen mensen in kaart. Op basis van de postcode kon worden nagegaan wie met wie telefoneerde, hoe lang het gesprek duurde en welke taal er werd gesproken. 200.000 E

« On verra bien ce qu’ils en feront »

Géographe, professeur à l’UCL, Isabelle Thomas est l’une des auteurs de l’étude.

C’est rare l’utilisation de com© LALMAND / BELGA. munications téléphoniques pour une étude scientifique, non ?

Woedewas er in Spanjenadatde Fransepresident Nicolas Sarkozy naast Griekenland ook Spanje had genoemdals te vrezenvoorbeelden voor een mislukt economisch en financieel beleid. “Ziedaar de situatie van Spanjena zevenjaarsocialistischeregering”, had Sarkozy gezegd tijdens de presentatie van zijnprogrammavoorzijnherverkiezing. Hij waarschuwde daarmee tegen de verkiezingvan de socialistFrançoisHollande. “We willen toch niet dat ons hetzelfde staat te wachten als onze Spaanse vrienden.” Maar de boosheid in Spanje kan niet verhullendat het lander economischbijzonder slecht aan toe is. De verwikkelingen afgelopen week in Spanje maakten een einde aan de rustrondde eurocrisisdie er kwam na de Grieksetragedie.In Europagroeidede vrees

Lisbonne, l’Otan entame Het resultaat van A het onderzoek toont aan sa datmue onze sociale contacten de administratieve grenzen abonnés en un an pour le A van de provincies overstijgen. Blondel komt bovendien tot de conclusie dat we niet tien maar « Voocorder » Pédophilie : zeventien provincies zouden moeten hebben. Ce n’est pas unique, mais c’est rare, en effet. Il n’est pas courant de disposer de telles données. J’ai travaillé avec deux ingénieurs qui m’ont fourni un matériel extraordinaire que j’ai pu mettre en musique cartographique. Si l’on ne travaille pas souvent avec cela, c’est que l’on a beaucoup de difficultés à gérer statistiquement ces matrices de flux énormes. Au départ, il y avait

J’espère que ce sera un outil d’aide à la réflexion et à la décision, oui. Je ne veux pas faire de politique, chacun son métier. On verra OL.M. bien ce qu’ils en feront…

le Vatican prépare des directives

Uitzondering is Limburg

P.10 Le pape Benoît XVI va adresser des directives à tous ses évêques dans le but de protéger les mineurs.

In veel gemeenten bellen de bewoners met contacten uit aangrenzende provincies. Zo tellen de rances de l’opérateur. Antwerpen en Oost-Vlaanderen elk drie grote regio's waar de bewoners telefonisch met provincies elkaar communiceren. De Vlaams-Brabanders bellen dan weer met Oost-Vlamingen, Antwerpenaren en Limburgers. Een uitzondering is Limburg, waar de sociale contacten bijna Essayez la nouvelle ix20 helemaal binnen de provinciegrenzen geschieden, met uitzondering van een stukje oostelijk en long et en large et tentez de la gagner! Brabant. De West-Vlamingen splitsen zich ten slotte op in twee sociale regio's, een kustregio en Voir p.15 P.2 & 3

LE SECRÉTAIRE GÉNÉRAL de l’Otan, Anders Fogh Rasmussen, ici avec Barack Obama, a présenté à Lisbonne la nouvelle stratégie de son organisation. © EPA.

NOTRE DOSSIER

SCIENCES&SANTÉ

43

16648720

16773680

Plis et replis de la Nature

Les structures plissées comme celles que présentent les montagnes, notre cerveau – ou encore les rides de la peau – résultent d’un mécanisme identique. Le laboratoire « Interfaces et fluides complexes », de l’Université de Mons, vient d’en découvrir les secrets de fabrication. Ce qui permettra de mieux prédire leur apparition.

Trouvez votre courtier indépendant sur www.brocom.be

www.lesoir.be

Aide à la jeunesse / Un rapport de la Fondation Roi Baudouin évalue la loi de 1965 et se penche sur le placement des mineurs

4BX

Placer les jeunes délinquants, ça sert à quoi ?

19/11/10 23:56 - LE_SOIR

L

du 20/11/10 - p. 1

’enfermement n’est pas la seule voie possible pour répondre à la délinquance juvénile. La législation actuelle prévoit une série de mesures * ! $ " " # % !

Verschillende ouders hebben hun kinderen uit de Antwerpse crèche Kai-Mook gehaald, nadat enkele verzorgers bekend maakten dat de kinderen er niet goed werden verzorgd. ‘De kinderen kregen ongezond en onvoldoende te eten en moesten op houten planken slapen.’ De bom ontplofte twee weken geleden. VerzorgerJonasPeeters(23)staptetoennaar deoudersvan de kinderendiedecrècheover devloerkreeg.“Ikkon hetnietmeeraanzien. De eigenares bleef maar kinderen toelaten, terwijldaareigenlijkgeenplaatsvoorwas.Ze loog de ouders ook voor. Ze verzekerde hen dat de kinderen elke dag vers voedsel kregen, maar niets was minder waar. Alles kwam uit blik of dozen. En op was op. Vaak moesten kinderen het met koekjes stellen.” SophieCuylits,mamavan de 19 maanden oude Lulu Bervoets, zag met eigenogen hoe hetfoutliepin Kai-Mook.“Hetleekonsaltijd een heel leuke, gezellige crèche, maar na enkele geruchten ben ik eens onverwacht op bezoek geweest. Toen ik binnenkwam warenzehetetenaanhetbereiden.Eendoos mousseline en twee kleine blikjes erwtjes voor twintig kinderen. Sommigen kregen maar enkele lepels puree. Waarom mijn dochter al vier maanden op hetzelfde gewicht bleef, werd me meteen duidelijk.” In de slaapzaal boven was het al niet veel beter. “Erwarenveelteweinigbedjesvoorde kinderen en op sommigen lag zelfs geen matras”, verteltCuylits.“Diekinderenmoesten gewoon op een houten plank slapen.” Samen met nog enkele andere ouders besliste Cuylits meteen om haar kind uit de crèche te halen. De drie verzorgers die er werkten, stapten op. Nadat stad Antwerpen twee klachten kreeg, voerde die donderdagochtend een onverwachtecontroleuit.“Er is iemandvan Kind en Gezin, een dokter en een stadsingenieur ter plaatse geweest”, zegt de woordvoerder van het kabinet van de burgemeester. “Ze hebben geen vaststellingen gedaan die een onmiddellijke sluiting zou verantwoorden. Maar de klachten die we binnenkregen,nemen we heel ernstigen we zullen deze zaak opvolgen.” Kind en Gezin benadrukt dat de crèche in kwestie niet erkend is bij hen. “Daarom is dat pas gestemdedecreetvoor de kinderopvang zo belangrijk”, zegt woordvoerder Ronny Machiels. “Alle crèches zullen in de toekomst een vergunning moeten hebben. En de voorwaardenzijnstreng.De eigenares van de crèchewou geencommentaargeven.

la nécessité de travailler * ! ." $ , (échange de bonnes pratiques entre, liens entre différents services, créer un poste de référent * . $ » par arrondisse-

La prévention, ce parent pauvre

La loi du 8 avril 1965 sur la pro-

fets indirects (absence d’estime de soi, ennui...). Et un besoin grandissant de prises en

68,5%

Overheidsschuld op hoogste niveau sinds 1995

23%

Werkloosheid, 1 op 2 jongeren werkloos

3,5 miljoen Huizen staan leeg

● Spaanse werklozen aan een arbeidsbureau in Pontevedra. © REUTERS dieten met lage rentes, ter beschikking gestelddoor Spaansebanken. Maar door de eurocrisis barstte ook in Spanje de vastgoedbubbel. Huizenprijzenzijn nu met een kwart tot de helft gedaald. Investeerders vragen zich af of de regering het aangekondigde programma van grote besparingen wel kan doorvoeren ter-

C opie de stiné e à be noit@ blonde l.be

Gautier Krings (mathématiques appli- en ne retenant que les communications par L’ESSENTIEL quées) et Isabelle (géographie) téléphone mobile qui trois mi71 ●ans, Philippe Mou- de ment vice-président de son parti, Thomas son levier de pouvoir.ont En pleine veilleux, des dépassent militants les exemplaiTrois chercheurs l’UCL utilisé un modèle mathématique inédit qui nutes, unres autre apparaît. Révélateur. reaux décidé d’annonpour connaissance de cause. et...visage quelques médiocres ». ontaanalysé pas moins deépauler 200 Elio Di Rupo ladans Belgique en sa ensembles cohé- Tout frontière linguistique est cer qu’il lâche la présiden- les négociations redessine communautaiDans lette de démission, qued’abord, C’estla Rudy Vervoort, bourgrents. * # # " ! . $ " une réalité téléphonique : seules 2 % des millionsbruxelloise de communications. ce de la fédération du res, jusqu’à la formation du gou-# nous publions, il explique qu’il mestre d’Evere, qui le remplace. #! ' " "# % ". & " # " communications analysées vont du Nord PS. Une décision qui sent fin communes vernement, il passe clairement la part « sans fleurs ni couronnes » Pour un an. ■ ● Bruxelles etlacinq " " $ ( -" & # " & $ " $ vers le Sud ou vice versa. La communauté de vie politique. Et c’est le francophones. cas. main. En effet, en quittant le leaqu’en il a à facilités sont ! ! " # $ & et! .explique " $ & % , vingt expli-ans, germanophone, elle, fait bel et bien partie ! P.4 L’ENTRETIEN Car, même s’il reste provisoire- dership de sa fédération, il lâche rencontré « des gens merque Isabelle Thomas. " # ! # % # # de l’espace francophone. # $ $ " .# # " ' $ & ' * ! ." $ " ! $ & " "# . t si la Belgique administrative et poli- $ $ "" " # $ ! ! # ! , prolonge Isabelle Thomas. % tique correspondait… aux flux de la & ! $ & " # $ ! , $ " # ." .! .! téléphonie mobile. La Région bruxel! $ & " "$ ! " & " $ "# " loise serait élargie à 47 communes des Bra- La « vraie » Région bruxelloise " " , Le fameux « corridor » voulu L’hinterland social bruxellois des commu- par les francophones, une réalité téléphonibant flamand et wallon. Ou, à tout le moins, lors que camp belge, nications de GSM s’étendrait à 47 commu- que. Et ce n’est pas la seule conclusion politielle rejoindrait l’espace francophone en le Yves Leterme a tenes en detête, Meise et Asse à Perwez et Genappe quement sensible : les communes d’Espiercompagnie de cinq des six communes à facinu une nouvelle fois àpar ras-Rebecq et Zaventem. * en passant lités de la périphérie (sans Wemmel). res-Helchin d’Herstappe et de… Fourons "# ! pla# # # analyse la géogra- sont liées elles aussi à la Wallonie-BruxelC’est une étude scientifique onquant ne peut surer aux menaces qui $ # ! " .# $ " # . #! . "$ ! plus rigoureuse qui illustre ce constat. les. Conclusion de l’étude, qui sera diffusée nent sur Trois l’avenir phe. des implanta" " " l’or" " $ professeurs et doctorants detions l’UCLde ont ana- en Belgique, lundi sur le site « brusselsstudies.be » : on l’Otan P.23 lysé & pas 24moins Voici unmillions #0! # " " # pourrait tenir compte des résultats * de 200 de communi$ ! ganisation a adopté ! vendredi à " «" " concept " " $ & , cations mobiles passées entre le 1er octobre ! " # "#! # % # . # Lisbonne son nouveau an, Voo se lançait OLIVIER MOUTON 2006 et le 31 mars 2007. Vincent Blondel, Si l’on tientqui compte du critère de la durée, $ $ , .■ stratégique », un document dans la bagarre avec va déterminer l’évolution de l’organisation au cours de la Belgacom sur l’offre prochaine décennie en la dotant « triple play » (inter- notamment d’une défense contre les missiles balistiques, a net, télé, téléphone). annoncé son secrétaire général Anders Fogh Rasmussen, en Aujourd’hui, les chif- brandissant ce texte devant la fres de vente dépas- presse à l’issue d’une première de travail des dirigeants sent toutes les espé- session des vingt-huit pays. ■ !

SARA VANDEKERCKHOVE BRUSSEL

Le Soir Vendredi 1er octobre 2010

Deux millions et demi de vaccins contre la grippe saisonnière sont disponibles en Belgique actuellement, a indiqué jeudi Mark Van Ranst, du Commissariat interministériel Influenza. C’est un nombre similaire aux autres années. © AFP.

CINÉMAS 21 BOURSES & MARCHÉS 30-31 BONS À DÉCOUPER 33 THÉÂTRES 48 BÉDÉ, JEUX & HOROSCOPE 49 TÉLÉVISION & LOTERIE 50-53 MÉTÉO & PETITE GAZETTE 54 NÉCROLOGIE 61

Antwerpse crèche die kinderen ‘op planken’ liet slapen

wijl een recessie aan de deur staat en de werkloosheidhogetoppenscheert.Dinsdag maakte de Spaanse minister van Financiën, CristobalMontoro,dedetailsbekendvan het besparingsplanwaarbij27miljardeuromoet worden bezuinigd. Daarmee moet het Spaanse deficit van 8,5 procent worden teruggebrachtnaar 5,3 procentvan het bbp.

Gevreesd wordt dat de scherpe bezuinigingen die de regering-Rajoy moet doorvoeren zullen leiden tot een economische inkrimping en, zoalsbij Griekenlandhet geval was, een negatieve spiraal waarin het land verzeild geraakt. Toch zei de Spaanse regering gisteren geenberoeptezullendoenophetnoodfonds van de EU. “Spanje is in staat om de problemen alleente overwinnen”, zei ministervan Economie Luis de Guindos. Maar de minister zei ook dat de huidige situatie op lange termijn niet houdbaar is.

l

+

!

!"

7 4 /8 ) . + 7 ) . + : 7 8 * + 1# 4 3 9' 3 ' 1> 8 B 5 1: 8 * + 2 /11/4 3 8 * ' 5 5 + 18 2 4 ( /1+ 8 + ( ' 8 8 /3 9B1B5 . 4 3 /6 : + ( 7 : = + 114 /8 8 B9+ 3 * ( /+ 3 ' : * + 1A* + 8 )4 2 2 : 3 + 8

!

' 3 8 1+ 8 * B( ' 98 . 4 : 1+ : = 8 : 7 1' ) 4 2 2 : 3 ' : 9' 7 /8 ' 9/4 3 ; 8 7 B- /4 3 ' 1/8 ' 9/4 3 1' ,7 4 3 9/C7 + 1/3 - : /8 9/6 : + 4 : + 3 ) 4 7 + 1B1' 7 - /8 8 + 2 + 3 9* + 7 : = + 11+ 8 ; 4 /) / : 3 + B9: * + 5 4 : 7 1+ 2 4 /3 8 4 7 /- /3 ' 1+ 6 : / 3 + 2 ' 3 6 : + 7 ' 5 ' 8 * + 3 /3 9+ 7 5 + 11+ 7 5 1: 8 * : 3 " 7 4 /8 ) . + 7 ) . + : 7 8 * + 1# @ $ /3 ) + 3 9

7 + * + 8 8 /3 + 8 /1+ = /8 9+ * + 8 + ,,+ 98 * + ,7 4 3 9/C7 + 8 A1/3 9B7 /+ : 7 * + 1' + 1- /6 : + + 96 : + 18 8 4 3 9 /18 4 : 7 ) + ,' /7 + 1+ 8 97 4 /8 ) . + 7 ) . + : 7 8 4 3 9 94 : 9* ' ( 4 7 * * B) 4 : 5 B 1+ 8 5 ' ) + 9B1B5 . 4 3 /6 : + ( + 1-+ 8 : 7 1' ( ' 8 + * + 1' ,7 B6 : + 3 ) + * + 8 ) 4 2 2 : 3 /) ' 9/4 3 8 + 3 97 + ) 4 2 2 : 3 + 8 7 + 2 /+ 7 ) 4 3 8 9' 9 ; " ! 3 3 ). 3 4? ,? 0( / . ) 15%3 # / - 0/ 3 ? 3 $ % > # / - - 5. %3 ! 0 0! 2! )3 3 %. 4 . ! 452%,,%- %. 4= 7 + 1C; + 3 9 1+ 8 8 ) /+ 3 9/,/6 : + 8 : 97 + + 3 8 + /- 3 + 2 + 3 9 ; ,%3 ' 2/ 50%3 $ %# / - - 5. %3 3 / . 44/ 5* / 523 # / . 3 4)45? 3 $ %# / - - 5. %3 ! $ * ! # %. 4%3 = ' 3 ' 1> 8 + * + 1' ,7 B6 : + 3 ) + * + 8 ' 5 5 + 18 ! 5 + 7 2 + 9 B- ' 1+ 2 + 3 9 * ' 99+ 8 9+ 7 6 : + 1' 1' 3 - : + 7 + 5 7 B8 + 3 9+ : 3 + ( ' 7 7 /C7 + ,4 7 9+ + 3 2 ' 9/C7 + * + ) 4 2 2 : 3 /) ' 9/4 3 8 9B1B 5 . 4 3 /6 : + 8 + ,' /9 ; ,! & 2/ . 4)B2%,). ' 5)3 4)15%%3 43 5)6)%0! 2,%3 ,)- )4%3 $ %3 ; " ! 3 3 ). 3 4? ,? 0( / . )15%3 = > , %8# %04)/ . $ 5 " ! 3 3 ). $ % 258%,,%3 %4$ %3 # / - - 5. %3 > & ! # ),)4? 3 $ 3

7 : = + 11+ 8

! 58 # / - - 5. %3 - ! )3 ? ' ! ,%- %. 4> $ %3 # / - - 5. %3 $ )2%# 4%- %. 4 # / . 4)' 5A 3 %4 # % 15%,,%15%3 / )4,! $ )2%# 4)/ . ' ? / ' 2! 0( )15% ! 6%# 4/ 54%& / )3 5. %%84%. 3 )/ . 3 0! 4)! ,%0,53 & / 24%6%23 ,% 2! " ! . 47 ! ,,/ . 15 ), %. ' ,/ " % 4/ 4! ,%- %. 4> , %8# %04)/ . $ % )6%,,%3 %4$ % $ %58 # / - - 5. %3 > , %842@ - % 3 4 ? ,? # ). % %4 20 ! 5# ( % = ' 7 2 / 1+ 8 ) 4 2 2 : 3 + 8 + 3 - 14 ( B+ 8 ,/- : 7 + 3 9 ' /3 8 / ' 1 $ /1; 4 7 * + & ' ; + 3 9+ 2 " + 7 ; : 7 + 3 7 ' /3 + 1 11+ : * 99/- 3 /+ 8 % ' ; 7+ + 7 < + ? 4 : + 3 ) 4 7 + 4 * 4 /- 3 + 4 : 7 1+ 8 ) . + 7 ) . + : 7 8 ; ,% " ! 3 3 ). $ % 4? ,? 0( / . )% " 258%,,/ )3 %3 4 > , )- ! ' %$ 5 & / . # 4)/ . . %- %. 4$ %3 / . ! ' ' ,/ - ? 2! 4)/ . " )%. 0,53 ? 4%. $ 5 15% ,%3 # / - - 5. %3 " 258%,,/ )3 %3 4/ 54! 54/ 52$ % ,! # ! 0)4! ,% ! 6%# 5. % %84%. 3 )/ . 3 0! 4)! ,% 0,53 & / 24%6%23 ,%3 5$ = B6 : /5 + 8 + 8 9B- ' 1+ 2 + 3 95 + 3 ) . B+ 8 : 7 1' * : 7 B+ 2 4 > + 3 3 + * + 8 ) 4 2 2 : 3 /) '

8 + * + 8 8 /3 + 3 9) 1' /7 + 2 + 3 9 1: 3 ' : 3 4 7 * + 9 1' : 97 + ' : 8 : * * : 5 ' > 8 ; ! 2- ) ,%3 0,53 $ % - ),,)/ . 3 $ % # / - - 5. )# ! 4)/ . 3 ! . ! ,9 3 ? %3 3 %5, 6! $ 5 ' 2/ 50% . / 2$ ! 5 ' 2/ 50% 3 5$ %4 $ 5 ' 2/ 50% 3 5$ ! 5 ' 2/ 50% . / 2$ . $ ! 542%3 4%2- %3 02B3 $ % $ %3 # / - - 5. )# ! 4)/ . 3 4? ,? 0( / . )15%3 3 % & / . 4 %. 42% $ %3 ! " / . . ? 3 $ 5. - @ - % ' 2/ 50% * B9' /11+ 3 9 1+ 8 97 4 /8 ' : 9+ : 7 8 %3 # / - - 5. )# ! 4)/ . 3 3 %- " ,%. 4 $ / . # & / 24% - %. 4). & ,5%. # ? %3 0! 2,! 02/ 8)- )4? ' ? / ' 2! 0( )15%%403 9# ( / ,/ ' )15%= ! + ) : 3 * 4 1+ * B) 4 : 5 ' -+ 3 4 7 * 8 : * 8 : /9 1' ,7 4 3 9/C7 + 1/3 - : /8 9/6 : + A1+ = ) + 5 9/4 3 * + ) 4 2 2 : 3 + 8 A,' ) /1/9B8 4 7 2 /8 % + 2 2 + 1 ; ,%3 # / - - 5. %3 > & ! # ),)4? 3 $ %,! 0? 2)0( ? 2)% " 258%,,/ )3 % 2/ ' %. " / 3 2! ). ( %- ). + % " %%+ ( / $ % ! ). 4 %. B3 % %: %- " %%+ 3 / . 44/ 54%3 2%' 2/ 50? %3 ! 6%# ,%3 # / - - 5. %3 $ 5 3 5$ $ 5 0! 93 = 8 4 : 1/- 3 + 1B9: * + ' 3 8

[Ratti et al., 2010]

[Calabrese et al., 2011]

France

May 2010

July 2010

Le mobile, reflet des frontières françaises LE MONDE SCIENCE ET TECHNO | 16.12.11 | 19h21 • Mis à jour le 16.12.11 | 21h13 A l'heure des communications tous azimuts, SMS et téléphone portable, on ne s'est finalement guère affranchis des distances. 85 % des communications se font au sein d'une région et seulement 15 % en sortent. Bref, les Bretons parlent

France

94 departements (est. 1790)

22 regions (est. 1919)

France

94 departements (est. 1790)

22 regions (est. 1919)

Charles de Gaulle resigned the presidency in 1969 following the rejection of his proposed reform of local governments in a nationwide referendum.

2

0123 Samedi 17 décembre 2011

SCIENCE & TECHNO

actualité

Le mobile, reflet des frontières françaises C’est à l’échelle de la région qu’on passe le plus grand nombre d’appels, selon une étude des transmissions entre antennes-relais. Une illustration du potentiel de la toute jeune science des réseaux

télécommunications|

David Larousserie Lyon, envoyé spécial

A

85 % des communications se font entre régions et 15 % à l’extérieur

l’heure des communications tous azimuts, SMS et téléphone portable, on ne s’est finalement guère affranchis des distances. 85 % des communications se font au sein d’une région et seulement 15 % en sortent. Bref, les Bretons parlent aux Bretons et peu aux Normands. Idem pour les Alsaciens, les Parisiens ou les Corses. Les «ondes »semblent s’arrêterauxfrontièresadministratives! Telle est l’une des conclusions étonnantes récemment obtenue par une équipe de chercheurs de l’université de Louvain, en Belgique, du Massachusetts Institute of Technology (MIT) aux Etats-Unis, et de l’Orange Labs, le laboratoire de recherche de l’opérateur de télécommunication Orange. Elle a été présentée, à Lyon, les 12 et 13 décembre, lors du colloque « Réseaux sociaux : des structures à la politique », organisé par le CNRS, l’Institut national de la recherche en informatique et automatique (Inria) et l’Ecole normale supérieure de Lyon. Plus de 1,5milliard de communications (SMS et voix) entre 17 millions de clients particuliers de l’opérateur recensées pendant six mois, en 2007, ont été analysées. Le contenu en était effacé, seuls restaient la

Les Bretons parlent aux Bretons et peu aux Normands. Idem pour les Alsaciens, les Parisiens ou les Corses durée et les lieux d’appel (identifiés grâce aux antennes-relais). Les chercheurs se sont demandés si des structures apparaissent au sein de cette gigantesque mer de données. «Les géographessavent bienque lescomportements sociaux se concentrent autour de points centraux. Nous nous attendions donc à découvrir undécoupage territorial. Mais nous pensions que ce serait le département plutôt que la région », explique Zbigniew Smoreda, sociologue de l’Orange Labs. Cette séparation est assez nette caraux frontières, leratio 85% – 15 % entre « extérieur» et « intérieur » ne tombe qu’à 75% – 25 %. L’algorithme de découverte des communautés ou des agrégats a donc trouvé que le meilleur découpage gomme les frontières plus anciennes desdépartements pourcollerà celles,plus récentes, des régions. Dans un agrégat, les clients échangent moult communications entre eux mais peu avec les autres. Cet algorithme, dit méthode de Louvain, a été inventé en 2008, et a depuis servi à traiter d’autres grands réseaux comme Twitter ou LinkedIn et leurs millions d’utilisateurs et « amis » (ou respectivement « nœuds » et « liens » dans le jargon du monde des réseaux mathématiques). En fait, la méthode permet d’obtenir le meilleur découpage, donnant des régions les plus denses possibles en liens. « Tous les trois jours je reçois des demandes

Pendant six mois, en 2007, les communications SMS et portables de 17 millions d’utilisteurs ont été collectées anonymement et localisées grâce aux antennes-relais. Un traitement informatique a regroupé ces échanges en zones riches en interactions internes mais pauvres vers les autres. Une ségrégation sociale (zones grisées) a été mise en évidence, correspondant aux régions administratives (traits noirs) et non aux départements (traits blancs). Ou presque. Rhône-Alpes est coupé en trois. Le LanguedocRoussillon « grignote » PACA. Tout come l’Alsace vis-à-vis de la Lorraine.

SOURCES : UNIVERSITÉ DE LOUVIN, ORANGE LABS

d’information à propos de cette méthode », témoigne Vincent Blondel, de l’université de Louvain et du MIT, co-inventeur de la technique. «Il y a dix ans, de tels outils n’existaientpas. Il y en a aujourd’hui des centaines, mais le nôtre est réputé comme étant le plus rapide. » Ainsi, si le nombre de nœuds du réseau est multiplié par 100, le temps de calcul n’est multiplié que par 200, alors qu’il aurait été multiplié par 10 000 pour des méthodes moins performantes. La France des mobiles n’a donc pas mis longtemps à livrer ses secrets. Avant elle, la Belgique était aussi passée à la moulinette de Louvain. La frontière linguistique Wallonie-Flandre était apparue assez nettement, tout comme l’îlot bruxellois plus multilingue.«Le test sur la France était intéressant car nous n’avions pas le biais

linguistique mais a priori un fort poids de l’administration », se souvient Zbigniew Smoreda. Pour le sociologue, la carte scolaire, donc les collègeset les lycées,orientefortement les flux d’interactions entre individus. Les adolescents parlent à leurs copains de la même zone; tout comme les parents. « C’est une sorte de formatage administratif des relations sociales. Ces liens entre espace et relations sociales intéresseront sûrement le marketing, soucieux de bien diffuser ses messages. » Il y a cependant des exceptions. Le nord Aquitaine parle peu au sud et réciproquement. Le Languedoc ne cause pas au Roussillon. Le département de la Haute-Loire est tiraillé entre Auvergne et Rhône-Alpes… Leschercheursont aussiconfirméuneloi quasi universelle bien connue des sociologues. Il

existe comme une loi de Newton de l’attraction universelle qui impose que le volume de données échangées entre deux entités, comme des communes ou des régions, est inversement proportionnel au carré de la distance entre elles. A taille égale, deux villes distantes de 100 kilomètres échangent cent fois moins de communications que deux villes distantes de 10 kilomètres. Cette loi fonctionne même pour des individus : la probabilité d’appeler un ami à 100 kilomètres est cent fois plus faible que celle d’appeler un ami à 10 kilomètres. « Cette loi de décroissance avait aussi été constatée auparavant sur les échanges économiques entre villes ou sur les lieuxde déménagement »,rappelleVincentBlondel. En choisissant pour logo la pomme, symbole de Newton, Apple avait donc vu juste.p

A la recherche des corrélations perdues

L

e volume des données engendrées par les activités humaines dépasse notre capacité à les traiter », rappelle Vincent Blondel (Université catholique de Louvain et MIT), qui travaille à la mise au point d’algorithmes performants pour s’y retrouver dans cette masse d’information. C’est aussi ce que propose une équipe américaine du Massachusetts Institute of Technology (MIT) et de l’université d’Harvard dans la revue Science du 16 décembre. Ces chercheurs ont élaboré une recette pour trouver des corrélations entre différents jeux de paires de données. Y a-t-il un lien entre passage des cigognes et naissance ? Entre pleine lune et criminalité? Plus sérieusement, ils s’intéressent à des bases de données de gènes, de bactéries ou de médecine, mais aussi… de base-ball.

Le but est de détecter, un peu à l’aveuglette, si des données a priori indépendantes le sont vraiment. La nouvelle technique a été comparée avec une méthode traditionnelle en statistique, appelée régression linéaire. Selon les chercheurs, elle a permis de trouver des corrélations insoupçonnées et plus complexes. Comme par exemple un lien entre obésité et revenus dans des îles du Pacifique. Des gènes ont aussi été mieux identifiés par leur méthode que par d’autres. Cependant, il reste à comparer cette méthode à des techniques plus sophistiquées. En outre, elle ne prend que les données deux à deux sans tenir compte de critères supplémentaires, ce qui est souvent nécessaire pour les analyses plus complexes. L’invention mon-

tre que l’exploration des bases de données devient aussi un enjeu de société. «Nous entrons dans une nouvelle période des usages de la statistique avec des collectes de plus en plus massives de données via les réseaux sociaux, par exemple, et toutes les traces que nous laissons. On ne cherche plus à faire des hypothèses pour les traiter mais on cherche seulement des corrélations, érigées en normes scientifiques. Les individus disparaissent au profit de profils statistiques »,constate Thomas Berns, philosophe de l’Université libre de Bruxelles, spécialiste des relations entre politique et traitement des données. Les géants du Web comme Amazon ou Facebook sont d’ailleurs à l’avantgarde de ce qu’il appelle le«gouvernement algorithmique». p D. L.

[Deville, Blondel, 2012]



Urban planning Control of epidemics Traffic optimization Demographic information Monitoring of development policy Crisis management ...

Population movements after earthquake and cholera epidemics

Data • • • • •

Webpages (content, graph) Clicks (ad, page, social) Users (OpenID, FB Connect) e-mails (Hotmail, Y!Mail, Gmail) Photos, Movies (Flickr, YouTube, Vimeo ...)

• • • • •

Cookies / tracking info (see Ghostery) Installed apps (Android market etc.) Location (Latitude, Loopt, Foursquared) User generated content (Wikipedia & co) Ads (display, text, DoubleClick, Yahoo)

• • • • •

Comments (Disqus, Facebook) Reviews (Yelp, Y!Local) Third party features (e.g. Experian) Social connections (LinkedIn, Facebook) Purchase decisions (Netflix, Amazon)

• • • • •

Instant Messages (YIM, Skype, Gtalk) Search terms (Google, Bing) Timestamp (everything) News articles (BBC, NYTimes, Y!News) Blog posts (Tumblr, Wordpress)

• • •

Microblogs (Twitter, Jaiku, Meme) Link sharing (Facebook, Delicious, Buzz) Network traffic

>10B useful webpages

(c) Alex Smola

Mobile phone D4D challenge Email to: [email protected] Subject line: «subscribe netmob yourname»

Social communities in mobile phone communication networks Vincent Blondel University of Louvain (Belgium) Aalto Complex Networks Factory June 2012

Social communities in mobile phone communication networks Vincent Blondel University of Louvain (Belgium)

Recommend Documents