Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido...

14
Usando Redes Aleat ´ orias na An ´ alise de Mobilidade Pedro O.S. Vaz de Melo 1,2 , Aline C. Viana 2 , Marco Fiore 2,3 , Katia Jaffr` es-Runser 4 , Fr´ ed´ eric Le Mou¨ el 3 , Antonio A.F. Loureiro 1 1 Universidade Federal de Minas Gerais, Brasil 2 INRIA, Franc ¸a 3 INSA Lyon, Franc ¸a 4 University of Toulouse, Franc ¸a {olmo,loureiro}@dcc.ufmg.br [email protected] {marco.fiore,frederic.le-mouel}@insa-lyon.fr [email protected] Abstract. The constant advancement of information systems has allowed more data to be generated and stored from the most diverse situations. It is fascinat- ing that, behind these records, we see the reflection of the environment itself, since every record represents a decision made by some entity. In this work, we modeled real-world scenarios of mobility from using temporal complex net- works. The analysis assumes that these systems are composed of entities able to interact in a rational manner, reflecting their interests and activity dynamic. In this direction, we propose a technique for analyzing mobility scenarios from random graphs. This technique examines how the real system would evolve if the agents’ decisions were random, and from there, you can check, for example, which edges are random and which are derived from social relationships, such as friendship or professional. Resumo. O avanc ¸o constante de sistemas de informac ¸˜ ao tem permitido que mais dados sejam gerados e armazenados a partir das mais diversas situac ¸˜ oes. ´ E fascinante que, por tr´ as de cada registro, seja poss´ ıvel ver o reflexo do am- biente em si, ou seja, alguma decis˜ ao tomada por alguma entidade. Neste tra- balho, s˜ ao estudados cen´ arios reais de mobilidade a partir de uma modela- gem usando redes complexas temporais. A an´ alise parte do pressuposto que esses sistemas s ˜ ao compostos de entidades capazes de interagir entre si de uma maneira racional, refletindo seus interesses e dinˆ amica de atividade. Nessa direc ¸˜ ao, ´ e proposta uma t´ ecnica para analisar cen´ arios de mobilidade a partir de grafos aleat´ orios. Essa t´ ecnica verifica como o sistema real evoluiria caso as decis˜ oes dos seus agentes fossem aleat´ orias e, a partir dela, pode-se verificar, por exemplo, quais arestas s˜ ao aleat´ orias e quais s˜ ao provenientes de relac ¸˜ oes sociais, tais como relac ¸˜ oes de amizade ou profissionais. 1. Introduc ¸˜ ao Trabalhos recentes sobre redes m´ oveis sem fio tˆ em analisado dados de mobilidade de indiv´ ıduos a partir de medic ¸˜ oes reais em cidades, como t´ axis em S˜ ao Fran-

Transcript of Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido...

Page 1: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

Usando Redes Aleatorias na Analise de Mobilidade

Pedro O.S. Vaz de Melo1,2, Aline C. Viana2, Marco Fiore2,3, Katia Jaffr es-Runser4,Fr ederic Le Mouel3, Antonio A.F. Loureiro 1

1Universidade Federal de Minas Gerais, Brasil

2INRIA, Franca

3INSA Lyon, Franca

4University of Toulouse, Franca

{olmo,loureiro}@dcc.ufmg.br

[email protected]

{marco.fiore,frederic.le-mouel}@insa-lyon.fr

[email protected]

Abstract. The constant advancement of information systems has allowedmoredata to be generated and stored from the most diverse situations. It is fascinat-ing that, behind these records, we see the reflection of the environment itself,since every record represents a decision made by some entity. In this work,we modeled real-world scenarios of mobility from using temporal complex net-works. The analysis assumes that these systems are composed of entities ableto interact in a rational manner, reflecting their interestsand activity dynamic.In this direction, we propose a technique for analyzing mobility scenarios fromrandom graphs. This technique examines how the real system would evolve ifthe agents’ decisions were random, and from there, you can check, for example,which edges are random and which are derived from social relationships, suchas friendship or professional.

Resumo. O avanco constante de sistemas de informacao tem permitido quemais dados sejam gerados e armazenados a partir das mais diversas situacoes.E fascinante que, por tras de cada registro, seja possıvel ver o reflexo do am-biente em si, ou seja, alguma decisao tomada por alguma entidade. Neste tra-balho, sao estudados cenarios reais de mobilidade a partir de uma modela-gem usando redes complexas temporais. A analise parte do pressuposto queesses sistemas sao compostos de entidades capazes de interagir entre si de umamaneira racional, refletindo seus interesses e dinamica de atividade. Nessadirecao, e proposta uma tecnica para analisar cenarios de mobilidade a partirde grafos aleatorios. Essa tecnica verifica como o sistema real evoluiria caso asdecisoes dos seus agentes fossem aleatorias e, a partir dela, pode-se verificar,por exemplo, quais arestas sao aleatorias e quais sao provenientes de relacoessociais, tais como relacoes de amizade ou profissionais.

1. IntroducaoTrabalhos recentes sobre redes moveis sem fio tem analisado dados de mobilidadede indivıduos a partir de medicoes reais em cidades, como taxis em Sao Fran-

Page 2: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

cisco (EUA), ou grandes campus universitarios, tais como USC, MIT, Dartmouth eUF. Em [Thakur et al. 2010], os autores observaram distribuicoes de similaridade daspopulacoes de usuarios moveis dessas bases de dados e verificaram que os atuais mo-delos de mobilidade falham em capturar o comportamento dos indivıduos de forma pre-cisa. Numerosos protocolos baseados em aspectos sociais damobilidade tambem temlidado com o problema de previsao de futuros contatos em redes intermitentes. Essasobras sao baseadas no fato de que o comportamento humano tende a ter um padraoespaco-temporal, repetindo locais e horarios do dia e mostrando algum grau de regu-laridade [Gonzalez et al. 2008]. Assim, pode-se avaliar, por exemplo, o potencial dosnos da rede para atuarem como disseminadores ou roteadores demensagens a partir demetricas de redes complexas, tal como a centralidade [E. M. Daly and M. Haahr 2009,Barbera et al. 2011, Kochem Vendramin et al. 2011].

O foco deste trabalhoe estudar cenarios reais de mobilidade a partir de uma mo-delagem usando redes complexas temporais. A analise parte do pressuposto que esses sis-temas sao compostos de entidades capazes de interagir entre si de uma maneira racional,refletindo seus interesses e dinamica de atividade. Chamamos esses sistemas deRe-des Complexas baseadas em Decisao (RCBDs), essas entidades de nos (ou agentes)e as interacoes entre os nos, de arestas. A principal caracterıstica de uma RCBDeque ela evolui de acordo com as decisoes tomadas pelos agentes desses sistemas, asquais sao guiadas principalmente por suas motivacoes pessoais [Backstrom et al. 2006a,Kumar et al. 2006, Leskovec et al. 2008, Mislove et al. 2007].Al em disso, RCBDs saocaracterizadas por terem um grande numero de vertices e arestas que apresentam umpadrao como, por exemplo, comunidades ou vertices altamente conectados, chamadoshubs[Albert et al. 1999]. Enquanto em uma rede simples, com no maximo centenas denos, o olho humanoe um instrumento de poder consideravel, em uma rede complexa,esta abordageme inutil. Assim, para estudar, analisar e caracterizar as redescomplexas,metodos estatısticos e algoritmos eficientes sao necessarios.

Este trabalho propoe uma tecnica para analisar cenarios de mobilidade a partirde grafos aleatorios. Resumidamente essa tecnica verifica como o sistema real evoluiriacaso as decisoes dos seus agentes fossem aleatorias. Mais especificamente, usa-se umalgoritmo que, a partir de uma rede real, constroi uma versao aleatoria contendo o mesmonumero de nos, arestas e distribuicao empırica do grau dos nos. Esse algoritmoe es-tendido para grafos temporais e, a partir dele, pode-se verificar, por exemplo, quaisarestas sao aleatorias e quais sao provenientes de relacoes sociais, tais como relacoesde amizade ou profissionais. Essa classificacao pode ser usada em diferentes aplicacoes.Por exemplo, o administrador de uma empresa de dispositivosmoveis pode usar estemetodo para detectar as relacoes sociais de seus clientes e, portanto, usar esse conhe-cimento para disseminar dados entre os clientes sem a utilizacao da infraestrutura darede [Daly and Haahr 2007, Hossmann et al. 2009, Katsaros et al. 2010]. Ao saber comoclassificar um encontro como aleatorio ou social, reduz-se o grau maximo de um no a umnumero viavel e escalavel, reduzindo o espaco de armazenamento.

Este trabalho esta organizado da seguinte maneira. As secao 2 descreve os traba-lhos relacionados. A secao 3 apresenta comoe feita a modelagem de cenarios de mobili-dade em redes complexas temporais e tambem como se constroi a rede aleatoria corres-pondente. A secao 4 discute tres possıveis aplicacoes para a modelagem proposta neste

Page 3: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

trabalho: classificacao de relacionamentos, predicao de futuros encontros e disseminacaode dados. Finalmente, a secao 5 apresentada as conclusoes e trabalhos futuros.

2. Trabalhos Relacionados

A analise dos aspectos sociais de sistemas complexose fundamental para a compreensaodas motivacoes por tras das acoes de suas entidades. Ao revelar as razoes por tras dasdecisoes,e possıvel separar os eventos aleatorios daqueles movidos por relacoes soci-ais. Em [Crandall et al. 2008], por exemplo, foi mostrado que aocorrencia de arestasna rede esta relacionada com as semelhancas entre os nos. Em outro exemplo interes-sante, [Backstrom et al. 2006b] mostra que a probabilidade deum indivıduo a entrar emuma comunidadee influenciada nao so pelo numero de amigos que ele tem na comu-nidade, mas principalmente pela forma como os amigos estao conectados entre si.

Os lacos sociais entre os usuarios tem sido amplamente ex-plorado em redes moveis oportunistas de modo a favorecer osservicos de rede. Os problemas considerados vao desde o encam-inhamento de mensagens multi-hop [Hui et al. 2008, Mtibaa et al. 2010,Mary Schurgot and Cristina Comaniciu and Katia Jaffres-Runser 2012] e multicast-ing, a seguranca da rede [Conti et al. 2010]. Em [Hui et al. 2008, Mtibaa et al. 2010],por exemplo, os autores utilizam metricas sociais derivadas de comunicacoes entreos usuarios para melhorar a eficiencia das decisoes de encaminhamento oportunistase limitando, simultaneamente, a sobrecarga da comunicacao. Todas as obras acimatentar explorar a regularidade e os repetidos padroes espaco-temporais esperado nocomportamento humano e tendem a ignorar as ligacoes aleatorias ou nao-sociais entre osusuarios moveis. Em vez disso, focamos na analise simultanea das relacoes aleatorias esocial entre os indivıduos.

Ate o alcance do nosso conhecimento, [Miklas et al. 2007] e [Zyba et al. 2011]sao os trabalhos mais estreitamente relacionados com o apresentado aqui.[Zyba et al. 2011] distingue usuarios sociais e itinerantes de acordo com seu com-portamento de mobilidade: regularidade ou duracao das visitas em uma determinadaarea. [Miklas et al. 2007] classifica as arestas entre amigose desconhecidos, sendo queencontros frequentes entre pares de nos caracterizam interacoes de amizade. Os autoresdefiniram empiricamente que indivıduos que se encontraram 10 dias ou mais dos 101dias sao amigos, outros sao estranhos. Neste trabalho usamos redes aleatorias para definiro limite que separa relacoes sociais de aleatorias.

3. Modelagem

3.1. Fundamentos

Dentre as principais caracterısticas verificadas em redes sociais reais, destaca-sea presenca de comunidades, que sao grupos de indivıduos fortemente conecta-dos entre si porque compartilham os mesmos interesses ou dinamicas de ativi-dades [Backstrom et al. 2006a, Kumar et al. 2006]. A formacao dessas comunidades so epossıvel porque a criacao das arestas reflete as decisoes sociais dos indivıduos, que geral-mente sao regulares e tendem a se repetir. Por outro lado, em uma redealeatoria as arestassao criadas independentemente dos atributos de cada no, ou seja, um no i tem a mesmaprobabilidadep de se conectar a qualquer outro no j da rede.

Page 4: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

Assim, uma metrica interessante para diferenciar uma rede aleatoria de uma redesociale o coeficiente de aglomeracao da rede. O coeficiente de aglomeracaocci de um noi caracteriza a densidade de conexoes proximas ai. Mais especificamente, ele medea probabilidade de dois vizinhos do no i serem conectados entre si [Newman 2003].Ele e calculado dividindo o numero total de arestas que existe entre os vizinhos do noi pelo numero de arestas possıvel entre eles. O coeficiente de agrupamento da redee a media cci, ∀i ∈ V . Por causa da existencia de comunidades, as redes sociaistem um coeficiente de aglomeracao alto, enquanto uma rede aleatoria tem um coefi-ciente de aglomeracao baixo, uma vez que as arestas sao uniformemente distribuıdas narede [Watts and Strogatz 1998]. No restante deste trabalho,esse conceitoe usado paradiferenciar redes aleatorias de redes sociais.

3.2. Redes Complexas baseadas em DecisaoA principal caracterıstica das RCBDse que as interacoes entre as suas entidades sao,geralmente, consequencia de decisoes semi-racionais. Escreve-se “normalmente” e de-cisoes “semi-racionais” porque qualquer sistema esta sujeito a eventos aleatorios e es-colhas irracionais. No entanto, uma vez que a maioria das interacoes ainda decorremde decisoes conscientes feitas por suas entidades, a evolucao de RCBDse significativa-mente diferente da evolucao de redes aleatorias como, por exemplo, redes de Erdos andRenyi [Erdos and Renyi 1960]. Assim, enquanto em uma RCBD as arestas sao geradasa partir de decisoes semi-racionais, que tendem a ser regulares e a se repetir, em umarede aleatoria as arestas sao geradas independentemente dos atributos dos nos, ou seja, aprobabilidade de dois nos se conectareme constante.

Considere, por exemplo, uma rede de pessoas e suas rotinas de mobilidade. Umainteracao entre duas pessoas ocorre se elas se encontram. Se Silva e Moreira trabalhamno mesmo escritorio e suas horas de trabalho sao de 8:00as 18:00, pode-se prever facil-mente que uma interacao entre Silva e Moreira ira ocorrer em torno de 8:00 durante osdias da semana. Entretanto, se o proprietario da empresa decide alterar o horario de tra-balho para de 12:00as 20:00, entao e quase certo que essa interacao tambem se moveradiariamente para 12:00. Tudo issoe baseado no fato de que acreditamos fortemente quetanto Silva quanto Moreira decidirao ir ao trabalho todos os dias pontualmente, ja queestee, provavelmente, a decisao racional para se tomar.

Por outro lado, a maioria dos cenarios esta sujeita a eventos aleatorios que podemdesviar o comportamento esperado dos agentes. No exemplo anterior, Silva pode esquecerda mudanca de horario da empresa e chegar ao trabalho no mesmo horario como antes,ou seja,as 8:00. Alem disso, ele poderia ficar preso no transito e se atrasar. O fatoe que,apesar de decisoes racionais serem regulares, as decisoes aleatorias podem muitas vezesocorrer tambem.

Formalmente, um agente pode executar uma decisao socialDs ou uma decisaoaleatoria Da. Ele tem uma probabilidadeps da execucao de uma decisao socialDs euma probabilidadepr = 1− ps da execucao de uma decisao aleatoriaDa. Intuitivamente,quandops ≫ pr, a rede normalmente evolui para uma rede social bem estruturada, coma presenca de todas as caracterısticas comuns de uma rede social vistas na secao 2, taiscomo a presenca de comunidades ehubs. Por outro lado, quandopr ≫ ps, a rede nor-malmente desenvolve caracterısticas de uma rede aleatoria, como as redes de Erdos eRenyi [Erdos and Renyi 1960].

Page 5: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

Este trabalho analisa tres conjuntos de dados publicos de mobilidade. O con-junto de dados da Universidade de Dartmouth [Henderson et al. 2004] (rede Dart-mouth), que contem registros de mobilidade de mais de mil pessoas dentro do cam-pus de Dartmouth, durante mais de oito semanas. O conjunto dedados do campus daUSC [jen Hsu and Helmy 2005] (rede USC), que tambem contem registros de mobili-dade em um cenario de campus universitario, com mais de quatro mil indivıduos durantemais de oito semanas. Finalmente, o conjunto de dados de mobilidade de taxis em SaoFrancisco (EUA) [Rojas et al. 2005] (rede Taxi), que contem registros da mobilidade de551 taxis dentro da cidade, durante quatro semanas. Em todos os casos analisamos asocorrencias de contato entre dois indivıduos, onde para cada eventoe registrado o inicioe a duracao do contato, todos na precisao de segundos. Nos registros de Dartmouth eUSC, dois indivıduos estao em contato se eles estao usando o mesmo ponto de acessosem fio(wireless access point) para se conectara rede do campus. Nos registros de taxi,dois indivıduos estao em contato se a distancia for inferior a 250 metros, quee o alcancemaximo de uma rede padrao IEEE802.11 [Piorkowski et al. 2009]. Mais detalhes dosconjuntos de dados que utilizamos neste trabalho sao descritos na tabela 3.2.

Conjunto de Dados Referencia Local Tamanho Numero de AgentesDartmouth [Henderson et al. 2004] Campus universitario 700MB 1156

USC [jen Hsu and Helmy 2005] Campus universitario 160MB 4558Taxi [Rojas et al. 2005] Cidade 161MB 551

Table 1. Conjunto de dados usados neste trabalho.

3.3. Grafo de Mobilidade

Neste trabalho, um cenario de mobilidadee modelado a partir de um grafoGt(Vt, Et),em que o conjunto de verticesVt contem os indivıduos que estao nos registros da basede dados antes do tempot e o conjunto de arestasEt representa todos os encontros queaconteceram antes do tempot. Assim, esse grafo evolui ao longo do tempo e consideratanto os encontros rotineiros quanto os encontros aleatorios entre dois indivıduos. Afigura 1 mostra retratos dessas redes em um dado intervalo de tempo. Observe comoedifıcil comparar as redes usando somente a visualizacao.

459

498

623

589

671

212

213

272

798

554

841

717

389

270

935 218

719

720

408

298

721

295

346

299

684

874

1018

296

683

463

571

458

742

462

630

1031

588

736

724

460

461

464

390

403

214

222

273

1012

1117

1111

625

225

910

762

759

743

594

646

763

364

406

274

271

642

409

898

595

413

722

472

410

216

756

73

411

331

276

414

419

664

520

494

365

468

327

372

264

266

574

368

1140

40

542

506

505

691

261 243

1019

259

696

634

976

927

709 620

729

873

525

499

226

846

491

760

1122

621

820

619

516

356

228

398

1121

807

519

533

147

145

90

91 92 60

593

1097

603 553

733

628

208

1080

148

392

443

395

551

694

93

182

1103

1089 399

402

275

878

1011

219

221

401

223

562

824

224

220

95

58

51

26

906

454

635

452

442

352

405

451

363

530

325

329

330

351

448

353

465

761

567

366

767

707

404

693

652

453

350

564

407

421

321 566

780

538

348

344

669 565

466

388

345

885

52

56

433

146

339

436

1030

753

867

473

1106

397

475

778

139

836

645

842

641

385

391

438

301

183

394

833

994

209

89 59 54

563

633

57

541

556

1137

393

521

387

569

1099 786

27

480

108

210

483

432

107

25

300

552

990

386

94

501 757

544

53

181

113

251

703

17

718

570

1051 24

422

384

1119

434

610

97 98

1084

338

417

725

755

420

416 332

354

792

322

415

714

253

983

607

418 524

1085

1136

700

437

929

471

359

349

227

252

412

1102 936

1020

478

815

255

559

250

75

76

1144

470

612

45

682

14

211

245

469

668

248

697 555 558

539

883

528

666

246

572

244

587

673 217

74

308

978

744

477

170

247

648

307

1139

240

233

1077

1132

984

1079

1037

890

784

706

134

1049

1044

972

998

968

997 1057

1008

973

949

1128

893

881

698

632

613

194

174

754

197

617

192

193

1126

199

63

1093

980 989

1092

1053

933

962

963

904 100

1101

191

198

1060

62

817

749

195

654

663

61

667

176

49

47

1024

1039

1023 1041

1043

1112

832

818

986

203

309

120

202

172

802

839

631

48

772

10

808

104

522

606

796 810 827

811

537

376

546

102

109

781

1067

930

728

72

912

860

69

866

144

455

7

143

456

337

937

954

941

921

801

1016

1052

788

819

1109

864

969

1094 747

800

995

901

215

971

1064

879

312

1133

911

905

1134

799

160

692

779 923 942

985

880

917

1061

987

909

914

925

946

876

887

230

1046

965 953

957

1070

1054

1091 1090

695

624

130

886

907

1108

1069

1129

1071

979 1006 1050 1032 849

764

582 903

888

1015

961

869

78

531

858

532

902 116 622

848

1038

1058

1042

1074

899

863

875

889

1025

1096

605

891

1027

1073

967 872

1026

897

592

1086 136

1098

1075

1048

1059 992

993

951 926

882

812

585

579

644

805

583

581

138

573

302

782

679

293

189

188

545

789

497

314

440

870 484

28

106

711

847

659

726

495

602

599

105

55

486

732

335

804

1000

439

441

292

184

1004

826

101

166

249

305

787

1095

966

727

731

591

511

256

167

16

23

396

1062

96

575

435

615

474

207

481

638

751 400

716

313

119

675

741

549

319

317

304

242

1047

1056

1124

837

626

232

79

794

918 939 996

590

932

838

131

828

865

1081

795

944

752

814

956

1029

1055

1040

1034

1009

938

896

734

660

449

77

311

168

231

959

601

1123

1063

947

132

135 71

457

831

677 662

1068 977

931

1013

970

861

862

908

535 241

280

1065

735 892

900

934 955

269 974

158

686

845

825

1114 190

608

702 1028

234

920

450

924

1100

649

597

821

1105

964

284

586

550

279

68

1066

1113

424

1045

114

46

518

361

793

681

916

982

238

112

103

277

1135

665

857

816

557

2

254

636

467

527

851

303

67

165 257

482 710

806

922

1104 1017

111

180

1143

737

514

87

658

1125

140

738

200

178

84

50

13

187

141

110

500

526

320 37

31

1107

1001

196

175

121

758

1110

676

1002

853

173

33

34

1118

627

653

1115

1141

643

766

177

561

797

529

122

118

80

126

124

179

1120

81

64

713

576

29

128

127

988

640

129

32

650

803

86

750

85

699

740

503

723

560

1021

548

82

35

8

204

685

769

765

485

670

730

513

88

83

9

11

958

201 877

315

316

12

30

614

310

123

36

504

496

479

125

791

294

770

206

507

336

1130

748

185

15

186

577

629

809

476

639

205

318

142

306

374

534

429

773

783

377

281

950

829

578

840

164

844

1033

161

163

913

1036 1035

945

1116

1014

715

1078

162 580

133

704

871

159

855

948

919

952

169

768

854

999

689

991

428

975

382

383

380

584

1003 1087

672

1007

137

852

291

894

509

1082

708

367

70

536

512

604

775

362

357

283

278

117

598

289

358

423

510 355

637

609 150

154

600

286

746 489

674

66 22

655

235

237

341

99

739

156

618

149

611 19

285

493

488

777

1131

771 490 155

6

785

430

1083

236

157

360

239

1076

20

21

5

1

830

835

823

822

884

378

379

381

540

680

282

688 1142

1072

508 515

523

745 895 1005

288

517

960 65

426

1138

678 705

1088 981 267

0

444

4

834

843

868

856

712

427

425

375

373

370

369

543 1127

262

263

43

940

41

268

260

44

258

3

568

813

229

647

928

850

265

39

38

502

943

446

447

333

334

371

690

687

492

776

774

431

790

297

661

701

323

343 326

324

651

340

342

328

487

596

171

656 347

1010

616

915

445

287

859

153

547 152

151

115

290

657

18

1022

42

(a) Dartmouth, 1 semana

2975

3109 3107

2693

2685

2757

2713

2743

2747

2465

2746

1842

1841

2718

3096

1681

2247 2798

2188 1454

2134 2379 143

2673

2711

2416

2906

1202 1245

3176

3322

3140

3074

2976

2982

3158

2764

3110

3136

3113

3065

3106

2732

2864

2689

2697

2684 578

3170

3214

3186

2402

3070

2403

3248

2874

2925

2971

2419

2968

2260

2148

3218

1985

1660

2430

3087

2292

2420

2408

219

1431

708 50

183

213 197

2700

2714

2223

919

3056

3254

280

1661

1500

983

1646

1528

1770

787

764

716

1667

2290

1867

1232

627

553

365

218

122

223

207

705

1276

518

2341

2242

1536

405

74

806

471

1457

1485

565

986

698

1856

343

312

179

2679

153

730

1686

767

1552

834 2813 84

49

1744

439

976

2703

425

2297

821

88

1547

1784

2474

1917

2445 2249

1636

384

2059 2030

2643

642

2606

2586

1571

1167

1396

8 2542 1340

3086 2346

885 2528

2965

2731

3271

2407

2486

2157

1927

1445

1778

1599

1257

1289 1342 2243

1429

2662

2511

3022 1987 503

168 2583

2062

974

2449

3249

2267

2998

3016

3323

1665

1492

402

3247

2895

2659

3142

3276

2839

3063

2409

1884

3

2455

2981 2256 3052

2934

2561

3099

1998

1272

1250

336

3143

2908

3302

2376

1945

2000

1986

1477

1226

3251 2799 2929

3192

3111

2503

1424

1383

1264 872

2655

2903

2208

2984

1994

1975

1993

1962

3303

2071

1876

2033

2073

2075

2450

3181 3018

3315

3199

2019

1822

1911

2017

1759

1848

2005 1032

2194

1461

1913

1920

1677

2043

2084

3121

1918

1721

1891

1783

1786 1704

1742

1907

1225 999

1132

924 1094

894 784

1814

3025

3042

1868

1834

3080

2102

2222

1416

988

1103

2429

1140

2177

1163

375 337

508

1925

1092

524

29

855

1933

2949 2913

159

1056

2809

1458

1949

2774

996

826

447

250 214

68

376

228

1639 911

820

2133

1792

2002

209

182

395

966

28 1160

2054

2824

2736

2616

1367

2995

2372

1137

2083

2966

2594

2628 2946

2459

3273

2961

2113

1735

967

1992

1808

2028

1198

2201

2215

1748

1556

2771

1878

3311

1804

1858

2072

102

832

2969

1241

1937

1699

2724

692

1466

588 1470

1044

1707

3166

441

190

186

2902

2375

2388

2018

1568

421

142

2960

1581

1767

1793

146

1462

888

940

3151

1908

991

166

18

1585

1882

2285

3266

2380

1750

1150

325

1155

2768 994

2709

1114

1694

1120

1067

2326

208

703

1473

1196

2386

1769

2741

229

217

149

1474

2726 2802

1577 3104

310

399

1594

582

1134

453

1231

681

189

216

17

544

786

512

805

285

165

169

682

80

628 242

1029

971 2710

749

793

1055

248

180

961

134

61

222

437

1031

776

3115

1411

2993

889

2317

3324

3299

2053

2983

2180

2898

2534

2779

3267

2646

3023

3265

2600 2147

90

2985

3038

2630

3006 2098

2066

1828

1849

1674

2358

2522

2364

3286

2142

2149 1386

2130

2216

2126 2023

706

666

641

620

500

2884

3064 2945

2793

715

1795

1194

380

256

2550

2858

1676

1398

63

2182

2382 1218

2783

393

2863

478

2128

1896

1960

1948

2996

2399

1290

151

2977 3253

3055

2933

2144

2365

2140

1369

1384

2962

3188

2942

677

3105

1079

1359

1365

533 592

674

640

2552

3135 686

495

2127

3088

2947

2183 2383

2150

2457

2361

3015

2366

2519

1979

2367

2829 2042

3284

2381 2039

3073

3281

2978

2944

2432

2145

2067 2124 1404

2360

2363

2357

2385

1387

3196

2937

3283

3288

1973

2515

3051

2889

498

555

691

3179

429

442

410

394

2911

3296

3293

2885

366

1672

1898

286

3244

2922

3297

3032

741

480

3041

1141

1130

1299 1255

1176

1171

1076

1268

1201

3268

3329

2564

3123

1889

2576

1897

2305

490

1558

1575

1972

1943

561

2020 2677

1125 2041

769

636

880

2537

477

412

372

566 721

1928 1311 1771

3312 1745

2772

1843 1587

1214 1306

417

1625 1309

2197

1007

751

1621

2368

1028 1560

646 1794

386

476 556

1718

1304 1736

591 1456

2355

1664

2916

2956 2955

2728

2538

542

3314

2682

2143

668

1265 2129

2136

3159

2172

1881

2900

1890

2761

1869 2213

684

1115

1025

1372

1128

1057

1220

897

845 796

818

722

732

1955

2389

2570

2418

1924

931

1863 1662

1085

1106

1254 1035

1001

920

809

712

3207

2132

2562

2125

2672

1553

1468

1483

1183

1734

1551

1550

1684 2123

1010

2168

2016

2184

3062

3059

2298 1815

867

1300

2309

2151

866

2236

2422

2733

3258

2334

2352

2347

2391

1900

1329

1361 2196

1773

2046 2543

1830

2121 1958

1260

1045

858

968

1190

2974

2669

2139

2374

3145

3177

2181

1997

2674

2001

3098

2931

1984

2158

2510

1877

2936

1685

2279

1953

2137

1720

2395

2013

2415

2435

2785

2580

2138

2239

1298

3069

2865

2639

2650

1494

1122

1428

1430

2691

2701

2502

2851

2920

801

2696

2668

2786

3147

2253

2269

2712

1444

1782

2289

1086

1954

2221

1341

16

3005

726

2917

1530

886

568

3239

2817

2670 2397

2986

1538

3100

2471

2954

2939

1696

3095

1048

206

2198

3082

2034

1991

1446

688

1669

2790

765

1121

2546

387

783

2092

2635

2804

2814

554

2170

3122

2320

1725

902

3261

1654

2972

2497

748

202

2792

401

2105

1942

1544

3120

420

2079

3224

2803

2796

2634

2844

3028

951

3097

2827

1450

1871

3246

3235

2940

2349

2932

3141

3027

2763

2878

2202

2303

3230

2224 2590

507

3327

3269 575

3185

2787

3256

2076

2189

1233

2055

3150

758

743

172

3134

1169

3089

2680

94

562

2559

1738

2760

2636

1107

906

2959

2526

1406

1613 3280

1246

707

2535

1240

802

226

1743

2480

1531

2769

1489

277

2530

2876

3180

1680

3112 1197

3102

1763

1844

2791

2927

3053

1968

816

293

2753

2935

2581

3237

3229

1899

1904

2176

673

101

2154

1453

2834

2683

1605

1516

2014

3004

1346

780

388

3076

1216

1803

833

2227

3240

3195

1005

1344

381

252

246

368

157

2060

1800

2926

3245

1995

1095 2301

2338

2632

2414

982

3257

2928 3093

2400

1855

1655

850

258

2240

2096 1420

2015 1358

1301

3146

2613

1789

1923

2037

79

944

2909

2056

1186

1512

2833 1479 734

1807

1527

1279

3182

1322

962

1112

2112

2896

1596

1015

2625

3178

1523

1370

900

2004

1042 2063

2501

2835

2390

2470 2572

860

1047

923

1886

3272

871

754

3259

2100

2074

2437

1448 1697

2219

1956

2484

2009

981

1996

2111

2398

1634

1011

1695

1791

2805

1845

1336

913

1090

926

874

2160

2371

2759

2343

2695

1946

2086

2477

1212

1711

12

2452

1248

2627

2873

1097

954

862

803

2300

3031

2483

964 2867 2275 2192

2027

1728

1207

2458

2448 2296 1688 1837

1579

695

1334

1046

848

2257

1573

1963

1930

2323

2518

1619

2348

2574

3007

2468

2742

2664

2598

3035 2332

2351

2304

2259 1967

2648

2702

1432

603

2081

2967

2992

2370

2621

1419

1354

876

2859 3206

1185

2417 2446 2319 2447

1812 1857

1447

2235

2681

2767

3242

2494

939

1080

408

1394

2310

2881

2516

1433

2871

2175 2231

1362

907

1020

1146

1172

1388

3278

1229

1227

3094

2988

2892

3068

2492

129

1957

106

2069

2930

3078

1816

3157

2162

2901

984

3208

2225

868

3079

2119

349

234

3250

1546

2912

3255

3148

1983

1833

2217

1511

1635

1267

714

2597

2218

2476

1038

2165

1191

1515

839

611

2567

2506

1915

1673

2274

2307

2690

1426

1069

956

2024

884

1818

1517

718

1244

263

3183

1436

1754

934

2554

99

115

2788

350

1755

935

1690 2812

1698

196

2234

846

1219

1879

211

1912

72

52

1521

2797 2500

2918

1906 2012

1400

2589

2316

1981

2315 2171

1714 693

2095

1522

1139

13

1251

916

1049

1321

892

1070

1409

1159

2276

1747

1414

1566

2328

965

1280

1135

950

605

201

268

3137

2146

1658

3217

2754

1331

1574

2775

423

69

1100

1009

729

1040

1243

612

3209

1357

2

782

2263

1041

1982

1238

273

247

135

3285

2720

1213

2838

1297

2808

3222

2280

2152

1701

735

1187

736

446

203

798

1153

2721

1799

560

3212

356

488

3174

1740

2923

2230

1839

2951

997

1113

847

772

9

3129

1181

2705

3234

2828

1320

1072

1678

3125

1593

2050

1938

55

2179

873

2818

2193

3260

1647

851

3282

2226

1364

2064

1959

1307

537

2715

540

616

598

2266 1821

2910

509

546

443

2238

1787

1768

2392

239 130

2943

525

645 664

148

1989

1706 1541

719

1287

656

296

306

57

2832

1950

2887

2868

711

1766

1862 2569

1537 969

2377

1570

1355 373

82

660

170

1850

531

1947

2232

2191

1666

1037

1893

1027

504

318

2675

1934

1548

1703

1627

2031

1136

1126 1104

482

2504

1063

391

998 2035

1302

174

141 110

329 701 1082 1535

1825

655 2206

355

47

864 1193

1017

1179

2325

2523

2883

2778

1564

1391

789

440

267

549

362

1691

1565

1109 177

1671

788

1761

576

720

133

243

344

2195 1012

406

2185 156

451

422

811

1117

367

323

898

240

178

825

1263

1105

1785

622

2205

284

1083

448 626

21 1093 882 2716 2756

1087 853

1154 914

594

624

322

638

1774 1509

2255

433

382

255

173

119

92

315

305

1490 925

1285

978 2877

1292

467

1580

795 1603

120

650 251

770

2800

1158

449

2229

176

164

86

30

1846

2816

670

2199 45

896

849

724

1236

1014

1151

1065

25

46

454

1348

947

1368

1591 678 1520

676 532

330 326

1713

1562

1499

2596

2687

757

697

338

249

220

2540

2545

972

1622

1123

2436

1476

1118

162

543

253

763

1266

232

205

457

552

288

171 435

1584 819

136

87

1066 1217

1481

2770

163

112

81

459

713

3144

2888

3275 2811

2952

3130

2836

2734

2825

2441

1205 1269

1351

1223

799

434

2830

3191 3124

1926

790 513

2356

2369

2362

2427

2671

2532

2068

2268

2302

3287

150

3085

771

1723

371

2780

1702

1705

289

1502

915

19

1487

2556

2722 1776

3233

1601

2919

1939

1557

351

671 1484

436

2725

2237

291

269

254

3227

893

3236

465

2513

959

704

791 1002

761

1752

1801

1471

455

262 27

1798

2135

1739

649

586

557

559

502

259

2730

2852

1679 2164 1700

515 514

59

1549

2169

2413

1903

669

633 583

473

418

683 1313 1192

1729 807

1071

584

245

1030

2820

359 545

2872 1910

24 15

257

2378 489

283 1472

3012

3238

654

2049

2061 1434

3300

385

265

2489

1990

2640 2963

2704

1013

2384

740

589

564

462

2116 2093

2036

2749

2869

2410

2261

2200

1586

530

56

1335 1004 2897

1905 1460

1324

474

428

989

2210

2321

1682 558 370

2938

2287

2507

2284

2273

2602

1327

3067

1964

1914

466

43

2153

1600 1563

2592

2204

1480

830 651

615

528

534

1075

1363

1330

987

2258

2915

1345 1894

411

2122

1180

822

486 574

494

1756

14

224

154

563

116

96

91

26

20

3090

1929

768

629

2156

2958

573 538

550

1486

1096 937

506

710

1518

1068

413

2207 2211

2038

2277

1861

599

3066 659

316

647

404

1819

1182

397

1189

766 539

1278 1966

475

124

93

275 510 785

415

200

167

1482 244 1852

957

1505

2166

272 551

233

2339

521

779

483

38

731

1124

430

797

194

699

432

1102

505

1469

1595

2313

1775

1597

977

663

270

187

22

278

231

2245 346

175

1640

301

339

261

452

653

617

608

340

469

161 89

630

585

458

725

444

456

302

292

160

158

426 618

438 1559

427

317

215

238

131

396

191

139

590

358

73 41

3034

2991

1610

2533

1608

1343

2665

2584

2765

2773 2099

3321

1475

2462 2571

2442 1039

3048

2591 3040

2997

2551

2354

2609

2491

2209

1781

1909

2011

2131

3081

2114

1061

1941

2246 2220

2619

1168

23

1215

2187

2393

2241

3316

2509

1670

1249

1247

3219

3307

3036

1737

2421

1811

1583

1052

2875

2438

2048

2254

2980

2359

2293

3153

2478

2294

3190

1539

3243

2337

2047

2094

2604

3128

3309

3326

3319

1209

2964

1333

416

3014

1498

3117

2278

1969

3057

1402

2087

1023

2283

3156

2463

2644

2846

2461

3039

3262

1443

814

39

2599

2633

2629

1961 2045

1648

1199

1175

657

690

3060

2512

2469

3045

1138

547

2525

2657

2485

2353

1823

1709

2473

613

1393

685

1054

309

147

1441

1860

1988

1242

5

973

2624 3184

1224

3001

1353

3020

2623

152

7

470

2826

3033

334

1317

3047

2006

2860

1870

2953

3046

2631

2115

1806

963

1746

2806

1326

1835

2638

2782

2856

3202

2531

3024

3263

2904

2845

723 1865

1940

2617

2424

2327

1427

3226

1895

3203

3193

2847

2862

3252

2823

2849

2706

2040

3000

2708

2312

1733

1437

1668

1618

2444

3043

1932

2110

2329

960

1554

1851

2029

1757

2907 1379

2434

541

1726

1919

2330

1840

3295

1764

10

3132

2861

2886 3037 3298 2233

1885

1464

3118

3010 3325

3306

3008

2622

414

100

3232

3304

3220

3044

3328 3021

3013

2645

3108

3091

3058

3200

1252

2051

3317

1152 823

1440

808

1142

3101

1630

1161

2605

2751

2999

927

3225

1692

3173 1050

34

2723

2994

601

1970

1820

1425

2107

282

1813

3175

1864

1545 1078

639

1859

1797

1788

1270

2058

1829

904

297

1716

1451

2819

1831

1008

2467

1817

1116

1021 689

1144

1222

1493

1177

3290

2784

2311

877

781

491

1412

2077

1131 1211

709

1024

361

2433

1439 2078

1059

742

694

313

335

237

51

1119

827 1101

665

980

2342 1258

643

675

3083

2052

2781

2941

1951

1753

1062

2214

389

1936

1435

2795

1352

975

1659

188

3072

2842

3154 1853

2850

3213

773

739

431

260

78

3216

2694

3189

2707

1779

192

3165

198

1675

840

2587

2899

936

887

979

869

747

324

279

71

3114

2626

3313

2251

2174

1708

1641

2003 2479

3103 1147

204

2641 424

1074

3223 2840

3152

2496

1651 632

398

54

193

400

390

945

750

953

97

77

227

522

1731

985

225

1722

1540

2893

2431

3310

1200

3194 2308

910

105

2575

2658

2737

1606

1148

1022

835 792

212

95

1976

2161 2536

2401

1632

2698 1129

623

450

516

230

1901

567

1892 2882

2021

2350

970 1256

1034

804

1491

1401

571

1626

1508 1488

2295

1872

497

572

300

1652

1088

2854

1642

2425

1188

3167

492

600

527

126

2250

2117

1578

1604

294

2521

2821 464

3168

863

403

1381

1033

311

199

409

727

948

838

702

377

132

118

48

1084

1081

672

1237

667

1098

460

328 319

304

842

753

949

943

738

687

364

333

1628

810

2558

774 2738

852

241

36

2517

777

1390 1127 2456

2070

519

184

2678

2740

2735

1689

461

44

607 1000

2744

658 1271 1854

345

104

1504

2855

1339

2739

635

1526 2539

1644

2306

1377 155

109

619

392

481 644

637

1110

596

595

83

1751 1208

2272

602

3277

3197

1204

363

341

276

144

2815

1525

2396

2344

1452

2853

2439

2270

3011

1408

383

353

140

2010 2573 794

1980

1780

2460

2286

2466

1338 1373

912

609 195

62

2333

1617

2336

1371

631

468

870

933

1965

369

2585

604

813

2563

2654

746 235

137

1162

117

1656

3241

2065

536

2264

107

320

958

879

121

76

3279

1296

1944 899 264

3054

2611

3301

2970

3139

2692

3092

3305 3211

2831

2314

2089

1609

1206

1637

3264

1410

3294

2745

2173

1283

2318

812

1455

2203

3198

993

1293 2411

2610

2577

2582

2252

2423 3084

2660

2026

903

1576

856

652 58 32

1977

2547

3228

1847 1765

1614

1497

1286

1382

1399

1262

3164

3003 3221

1058

1952

3030 2178 1421

1184 1602

2924

1165 1316

2453

1495

1295

1310

2601

535

1178 2607

2762 1569 2890 2801

2244

1974

3138

1507

1195 1145 895

775

717

752

496

2618

3274

2649

1730

2987 2837

517

484

1

1337

2548 2155

1529

3160

2766

2520

1350 378 111

4

3017

3127

1108

755 579

696

2789

1239 3172

3163

891

1496

1413

2608

1157

1916

1043

815

606

745

487

1089

2566 1203

2032

1649

1922

2464

511

85

1567

1465

3002

2406

1389

932

138

67

2271

2108

1588

123

1385 2291

2080

2481

75

321

1422

2505

2394 1838

2490

3026

952

778

374

2412 737

3308

1582

1235

1543

744

271

2527

2652

2752

2085

1532

2109

499

529

1467

2228

1805

2405

2345

3131

1173

128

60

1053

1612

844

2822

1873

463

1501

331 332

1478

1166

2794

1405

1018

1442

33

35

37

3291

1305

857

875

53

31

3320

1395

2843

1463

347

1836

1277

1291

2879

1273

2656

909

587

837

114

236

1019

1643

2894

878

65

762

2750

127

2921

1663

2948

2989

1288

922

859

472

281

1174

1164

1971

918

2870 1328

2973

883

759

307

829

942

1323

1133

548

1935

1274

1749

597

728

2212

1866 2288

2141

938

661

614

379

352

3029

2426

2498

921

2979

1796

2776

1633

881

581

3169

841

1650

2190

1332

3292

621

479 520

290

1392

1809

1615

995

526

3187

946

1620

3210

103

2914

2487

2265

2120

1732

2807

3133

2088

308

1719 1810

1741

3075

1449

3162

1760

2905

2676

2044

1832

1607

828

817

419

2637

3161

1715

2777

3171

1824 1772

1234

1710

1888

1683

3071

3149

2686

1513

1542

2104

1902

1693

1727

1016

930

577

2495

2603

3318

1561

955

3077

1883

1978

1875

2281

1261

348

113

145

928

1230

3050

493

181

1631

2614 2560

3061

1375

1156

1397

1514 1592

1376 1418

2022

2007

3289 1143

266

2719 2557

2727

700

905

3201 662

2103

3204

1598

1403

2699

2651 733 1534

1221 1687 1874 2387

1724

2957

2529

2091

1712

221

1360

861

625

354

210

2262

1510 2167

1790

941

1051

1827

3119 1657 2090

2340

1111

287

1623

3155 2578

2642 2990 2595 2299

2324

1325

1318

1315

570

1931 2593

2118 2404

1417

1253

854

760

593

299

342

2373

2499

2810 1073

2555

1060

360

357

298

2647 2322 1275

680 992

1629

407

295 98

2950

2717

2544

2758

2541

2688

2524

2331

2488

2553

2097

2335

990

2106 2451

2615

1638

1228

1308

2454 2482

2755 2428

2891

2514

3270

2565

1415

800

2666

1423

2620

2612

2508

1624

1645

1282

1303

648

2493

2568 3231

2472 2653

2579

3019

1294

1356

1259

634

1374 3049 1380

2440

2729

679

1887

580

890

2057

756

1999

824

1611

0

1590

485

1170

2248

2588 2549 2663

1064

274

1312

1572

1506

1524

2661

1026

836

445 314

108

1802

2282

1407

64 1758

40

11

3215

2101

1003 1210

1616

66

1314

2082

1880

2443

865

610

2475

1366

2159

1438

917

1319

569

2008

1503

2163

1077 1519

3205

3009

1149

303

1091 1284

1777

1459

501

327

523

6

908

1555

1347

1036

185

901

929

1589

1717

1349

2667

42

1826

3116

2857

2848

2841

1006

843

2186 1762

3126

1533

125

1099

1378

831 2748

2025 1281

70

1653

2880

2866

1921

(b) USC, 1 semana

274

371

236

511

35

482

323

539

347

543

120

98

19

16

13

227

216 189 355

439

44

53

81 191

524

175

122

99

205 512

497 125

299

386

538

341

479

535

194

93

29

276

315

364

414

506 370

475

468

314

416

288

332

343

459 457

397

178

239

328

181

445

173 504

478

228

513

258 54

26

27

211

238

310

349

193

137

78

15

3

161 231

221 284

281

133

50

17

9

183

73 384

271

233

58

222 454

37

23

412

518

514

392

452

337

292

241

79

46 30

403

393

435 369

297

242

199

203

88

404

458

361

492

313

223

208

201

49

12 63 249

85

473

449

407

423

363

408

446

474

428

252

184

141

4

499

266

356 280 505

444

165

151

74

157

383 406

286

42

182

20

531

542

429 263

158 196

325 267

365 421

526

304

420

336

508

160

146

31 11

275

489 334

72

527 59

298

226

76

498

247

354

401 324

278

206

138

75

77

66

25

188

424

348 516

316

493 174

131

64

34

301

388

210

360

385

186 123

82

65

121 486

270 187 139

434

395

517

117

476

491 285

330

214 179

38

24

212 507 198

305

481 277

311 494

145

153

389

115

219 467

269

372

366

381

312

456

245

113

83

91

326

220

197

261 112

338

295 95

86

60

373 471

519

279 377

549 487

352

62

319 243

440

455 218

213 180

171

132

447

480 36

2

207

402

118

260

501

378 462

307

240

333

89

318

309

537

170

126

427

142

396 541

41

14

190

71

209

460

391

107

148

39

164

451

308

450

411

94

431

342

256

172

200 143

106

6

485

147

490 101

124 287

159

425 488

464

244

410

47 399

466

327

70

135

119

109

345 90

152

351 430

84

443

306 442

136

437

375

114

111

1

426

232 272

215

217

110 87

472

250

293 368

346

530

32

69

533

144 441

264

57 28

7

5

225

128 166

470 251

154

130

51

21

546

398

273

532 67

545

100

540 45

10

350 163

382

415

259 510

167

387

61

22

495

149 134

544

436 254

463

68

419

339

422

320

469

52

322

296

290

405

379

357

80 43

359

358

417

302

374

432

55

262

204 331

230

484

418

155

105

33

8

394 521

509 380

255

168

496 224

550

522

335

548

536

515

525

551

234

483

503

257

340

321

529

185

48

(c) Taxi, 100 minutos

Figure 1. Retratos das redes em um dado intervalo de tempo.

O pesowt(i, j) de uma aresta(i, j) e modelado como a persistencia dessa arestadesde o tempo inicial1 ate o tempo correntet [Hidalgo and Rodriguez-Sickert 2008].Nos conjuntos de dados de Dartmouth e da USC, um intervalo de tempo e o perıodo de24 horas. No conjunto de dados dos taxis, um intervalo de tempoe de quatro horas. Por

Page 6: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

exemplo, no conjunto de dados de Dartmouth, considerando que os nosi e j se reuniramem 15 dias dosultimos 30 dias, entao a persistencia da arestaw30days(i, j) = 0.5, ou seja,em50% dosultimos 30 dias, os nosi e j se encontraram. A grande vantagem de modelaro peso da aresta como a persistencia em vez de, por exemplo, a duracao agregada docontatoe que, com a persistencia,e possıvel detectar relacoes regulares e de rotina entredois indivıduos.

O primeiro passo para analisar os padroes de mobilidade do grafoGt(Vt, Et) econstruir a versao aleatoriaGR

t (Vt, ERt ) do mesmo. Essa versao aleatoria deve conter as

mesmas caracterısticas topologicas do grafo real, ou seja, o mesmo numero de nos, arestase distribuicao empırica do grau. Dessa maneira, aunica diferenca entreGt eGR

t esta nasconexoes entre os nos. Enquanto emGt os nos se conectam “semi-racionalmente”, emGR

t a conexaoe feita de forma puramente aleatoria. Isso permite verificar com exatidao aextensao da aleatoriedade na mobilidade dos indivıduos nos cenarios analisados.

3.4. Geracao do Grafo Aleatorio

Para construirGR, e proposto o uso de um algoritmo de urna tao comum na geracao deestruturas aleatorias [Johnson and Kotz 1977]. O primeiro passo do algoritmoe colocarna urna, para cada no ni, di “bolas” marcadas com o identificadori do no, sendodi ograu do no ni. Depois disso, retira-se aleatoriamente da urna duas bolasbi e bj que estaomarcadas com os identificadoresi e j dos nos ni e nj. Sei 6= j e nao ha uma aresta(i, j) emGR, entao os nosni enj sao conectados emGR. Esse passoe repetido ate que(i) a urna esteja vazia ou que (ii) nao seja mais possıvel conectar os nos que estao naurna. Quando nao e mais possıvel conectar os nos que estao na urna, ha uma diferencaǫ ≈ 0.001% entre o numero de arestas deG e deGR, o que consideramos insignificante.Uma analise mais detalhada sobreǫ deixamos como trabalho futuro. Todo o procedimentode geracao de grafos aleatoriose descrito no Algoritmo 1.

Algorithm 1 : Gerando um Grafo Aleatorio GR a partir deG1:2: procedimentoGERAGRAFOALEATORIO(G)3: para todosnosni ∈ G faca4: para j = 1→ di faca5: urna.adiciona(j)6: fim para7: fim para8: tentativa← 0;9: enquanto!urna.vazia() etentativa < 1000 faca

10: i← urna.removeAleatorio();11: j ← urna.removeAleatorio();12: sei 6= j and !G.aresta(i,j) entao13: GR.conecta(i,j);14: tentativa← 0;15: senao16: urna.adiciona(i);17: urna.adiciona(j);18: tentativa← tentativa +1;19: fim se20: fim enquanto21: ǫ←urna.tamanho() /2×G.numArestas()22: fim procedimento

A partir desse algoritmo pode-se gerar um grafo aleatorio GR a partir de qual-quer grafoG. No entanto, neste trabalho sao analisados grafos temporais do tipoGt que

Page 7: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

evoluema medida que encontros entre indivıduos ocorrem. Como nenhuma arestae re-movida deGt e novos encontros sao sempre agregados, entao |Et+1| > |Et|. Assim,para construir um grafo aleatorio temporalGR

t , decompomosGt em t grafos de eventosG1,G2, ...,Gt, em que cada grafo de eventoGt contem somente os eventos que ocorreramentre os tempost− 1 e t. Assim,Gt = {G1 ∪ G2 ∪ ... ∪ Gt}.

Para gerar o grafo temporal aleatorio GRt com as devidas persistencias aleatorias

nas arestas, executa-se o Algoritmo 1 em cada grafo de eventoGt, criando assim o corres-pondente grafo aleatorio de eventoGR

t . Assim, o grafoGRt nada maise que a uniao dos

grafos aleatorios de eventos ,GRt = {GR

1 ∪GR2 ∪...∪G

Rt }. O peso, ou persistencia, aleatorio

de uma aresta(i, j) ∈ ERt e calculado dividindo o numero de vezes que(i, j) apareceu nos

grafos aleatorios de eventosG1,G2, ...,Gt port. A comparacao da persistencia real dos en-contros com a persistencia aleatoria permite, por exemplo, verificar a probabilidade de umencontro entre dois nos i e j ocorrerx vezes aleatoriamente em um determinado cenariode mobilidade.

4. Aplicacoes

4.1. Classificacao

Atraves da comparacao deGt comGRt e possıvel quantificar a probabilidade de uma de-

terminada persistencia de uma arestaw(i, j) ser consequencia da aleatoriedade de eventosou de uma relacao social real. Como os conjuntos de dados de Dartmouth e USC tem oitosemanas de registros de mobilidade, usaremos as primeiras sete semanas (base de treino)para classificar as arestas e aultima semana (base de teste) para verificar a eficiencia daclassificacao. Na base de taxis, que contem quatro semanas de dados,e mantida a mesmabase de testes de uma semana, ficando tres semanas para a base de treino. No final da basede treino, ha 175722 arestas na rede de Dartmouth,1287992 arestas na rede USC rede e142332 arestas da rede Taxi.

A figura 2 mostra a distribuicao cumulativa complementar da persistencia dasarestas tanto para a rede realGt quanto para a sua correspondente aleatoriaGR

t , em quet varia ate o fim da base de treino. Pode-se observar na figura 2-a que, para o conjuntode dados Dartmouth, as probabilidades de ter valores elevados de persistenciae ordens demagnitude menor para a rede aleatoria em comparacao com a rede real. De fato, enquantopara a rede de Dartmouth a persistencia das arestase quase uniformemente distribuıda,para a sua rede aleatoria correspondente nao existem arestas com persistencia superior a0, 4. Por outro lado, observa-se na figura 2-b que, para o conjuntode dados USC ha umadiferenca significativa apenas para altos valores. Isso indica que no cenario USC a mo-bilidadee superiora do cenario Dartmouth, favorecendo constantes encontros aleatorios.Finalmente, para o conjunto de dados Taxi, as distribuicoes de persistencia das arestas saopraticamente as mesmas. Nesse cenario, uma vez que a mobilidadee significativamentealta, mesmo aleatoriamente pode-se ter uma persistencia de100%.

Como mencionado na Secao 3.1, o coeficiente de agrupamento de uma redeeuma metrica interessante para verificar o quao social ou aleatoria e a rede. Portanto,a figura 3 mostra o comportamento do coeficiente de agrupamento para as tres redesanalisadasGt e seus correspondentes aleatorios GR

t ao longo do tempo. A figura 3-aindica que, para o conjunto de dados Dartmouth, nos primeiros dias o coeficiente deaglomeracao deG e GR e diferente em ordens de magnitude. No entanto, ao longo

Page 8: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

0 0.5 110

−6

10−4

10−2

100

Persistence

P(X

> P

ersi

sten

ce)

realrandom

(a) Dartmouth

0 0.5 110

−6

10−4

10−2

100

Persistence

P(X

> P

ersi

sten

ce)

realrandom

(b) USC

0 0.2 0.4 0.6 0.810

−6

10−4

10−2

100

Persistence

P(X

> P

ersi

sten

ce)

realrandom

(c) Taxi

Figure 2. Distribuic ao da persist encia de aresta (peso da aresta) para as tr es redes anal-isadas Gs e suas correspondentes aleat orias G

Rs.

do tempo os seus valores se tornam mais proximos, ja que mais encontros aleatoriosocorrem. Por outro lado, como vemos na figura 3-b, os coeficientes de aglomeracaodeG eGR para o conjunto de dados USC sao quase constantes ao longo do tempo. Noentanto, a diferenca entre eles naoe tao significativa quanto na rede Dartmouth, possuindoa mesma ordem de magnitude. Finalmente, os coeficientes de agrupamento das redes detaxi sao praticamente os mesmos, como observa-se na figura 3-c. Isso, juntamente como resultado mostrado na figura 2-c, indica queG e GR sao muito semelhantes para oconjunto de dados Taxi, ou seja, nesse casopr ≫ ps. Isso faz sentido ja que as decisoestomadas pelos taxis dependem da decisao do indivıduo quee levado por eles e, uma vezque taxis coletam indivıduos ao acaso na rua,pr ≫ ps. Por isso, a partir de agora so seraoanalisados os conjuntos de dados de Dartmouth e USC.

0 10 20 30 400

0.2

0.4

0.6

0.8

time (days)

Clu

ster

ing

Coe

ffici

ent

realrandom

(a) Dartmouth

0 10 20 30 400

0.2

0.4

0.6

0.8

time (days)

Clu

ster

ing

Coe

ffici

ent

realrandom

(b) USC

0 50 100 1500.2

0.4

0.6

0.8

1

time (10 min)

Clu

ster

ing

Coe

ffici

ent

realrandom

(c) Taxi

Figure 3. Evoluc ao do coeficiente de aglomerac ao das tr es redes analisadas Gs e suascorrespondentes aleat orias G

Rs.

Para as redes nao-aleatorias, ou seja, Dartmouth e USC, pode-se usar asinformacoes observadas na figura 2 para quantificar a probabilidadepw de existir umaaresta com persistencia superior aw e que seja consequencia de encontros aleatorios.Com isso, pode-se definir um limiteTw para a persistencia de uma aresta(i, j) de modoque, sew(i, j) < Tw, entao essa arestae classificada comoaleatoria, caso contrario, comosocial. Ao observar os valores de(x, y) da curva aleatoria na figura 2, pode-se definir umvalor deTw que torna a probabilidadepw de erroneamente classificar uma aresta aleatoriacomo social suficientemente pequena e aceitavel para uma determinada aplicacao. Porexemplo, se definirmosTw = 0, 4 para a rede de Dartmouth, entao a probabilidade de er-roneamente classificar uma aresta aleatoria como sociale≈ 0. E importante ressaltar queesse metodoe capaz de estimar a taxa de erros do tipo falso positivo para aclassificacao

Page 9: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

de arestas como sociais (pw), mas como a base de dados usada neste trabalho nao possui ainformacao sobre quais relacionamentos sao sociais, naoe possıvel estimar a taxa de errodo tipo falso negativo.

Uma vez que pode-se classificar arestas como sociais e aleatorias, pode-se veri-ficar como as redes evoluiriam caso fossem constituıdas somente por um desses dois tiposde arestas. Assim como foi feito na figura 1, a figura 4 ilustra retratos das redes de Dart-mouth e USC apos uma semana de interacoes, mas considerando apenas as arestas sociais(primeira coluna) ou apenas as arestas aleatorias (segunda coluna). Para a rede de Dart-mouthTw = 0, 2 e, para a rede USC,Tw = 0, 1.1 Pode-se observar que, enquanto as redesgeradas usando apenas arestas aleatorias sao muito semelhantes a uma rede aleatoria ge-rada, por exemplo, pelo modelo de Erdos e Renyi, as redes geradas usando apenas arestassociais sao mais similares com as redes sociais vistas na literatura,com a presenca clarade comunidades disjuntas. Note tambem como elas sao visualmente diferentes das redescompletas vistas na figura 1.

459

1012

458

460

798

630

623

588

461

462

463

1031

736

878

554

464

717 762

935

841

390

403

273

274

789

804

732

659

485

478

439

441

437

316

483

507

513

770

599

438

440

335

313

480

602

787

791

679

1062

614

481

479

486

476

484

748

336

318

539

496

474

629

314

337

751

185

315

482

319

317

495

205

615

639

188

1051

711

726

809

847

753

302

293

206

186

294

301

189

497

300

387

187

184

394

106

645

701

107

292

870

573

641

545

432

575

396

757

782

990

393

91

395

398

392

95

1080

145

338 448

502

445

657

444

915

157

446

447

1010

928

857

856

912

1072

775

773

776

777

601

1142

774

527

524

724

1117

541

593

386

276

389

271

272

295

684

683

671

874

592

275

270

733

628

562

1121

718

521

475

544

391

385

1018 1084

53

297

553

147

1030

89

148

397

94

90 563

96

473

92

93

52

842 610

867

299

59

58

807

433

633 552

551

519

790

97

98

146

339

436

501

824

139

60

786

298

533

1097

693

296

181

443

182

531

536

1086

399

1103

649

537

534

535

532

183

108

1106

778 54

1137

51

28

603

885

556

56

55

207

208

26

25

666

209

210

1119

694

57

943

661

1022

512

620

518

796

511

793

523

1

19

568

228

691

226

621

2

517

586

227

5

65

3

20

22

66

525

510

687

929

606

508

678

600

760

290

598

674

619

0

705

637

18

846

515

813

516

4

229

6

21

656

1029

1129

240

706

1139

311

1071

233

1132

1079

1070

1038

905

1091

801

828

788

692

457

1128

949

1052

1108

1093

972

1098

957

858

695 79

1039

1064

644

1034

907

925

764

1094

1068

1073

967

1060 1016

844

1033

1074

800 1026

852

845

881

962

944

1081

903

918

861

747

232

215

135

1078

1049

1035

234 946

987

872

779

980

1057

1075 1023

1096

1069

979

608 78

1109

1006

1056

1133

1047

1048

963

954

590

130

917

934

998

1134

1024

1040

938

819

449

241

77

794

1013

626

920

926

989

923

1009

1025

904

734

1112

1124

1027

865 242 838

997

456

1126

1041

455

577

1067

1066

941

914

951

919

890

1065

971

879 909

892 931

862

672

897

863

993

1046

908

956

854

891

886

855

893 937

950

1044

677

230

1015 1055 1058

1050

876

901

945

965

875

1061

899

869

805

136

955

913

1063

1036

1092

952 624

169

133

134

888

871

959

1059

190

814

984

1042

882

947

924

977

887

131

849

715

942

968

939

953

1037

864

969

752

896

948

100

702

831

985

1032

660

1008

995

158

662

784

812

735

168

795

902

889

974

581

579

132

1090

999

1003

583

163

159

137

799

825

921

1077

450

312

231

164

585 580

116

192

197

177

617

526

49

47

174

613

179 309

178

48

175

584

160

698

632

198

199

194

193

191

144

63

1014

1007

686

162

578

837

582

269

118

120

124

126

654

127

195

176

104

64

172

754

61

62

1143 988

853

1120

1043

500

561

121

310

730

1002

750

1107

832

1101

667

713

123

202

839

122

125

320

514

36

33

35

640

200

201

522

1000

818

203

37

658

504

204

769

129

109

128 31

529

685

808

986

766

802

663

817

740

110

140

32

631

548

34

737

749

958

1110 1054

961

973

900

932

996

992

1053

911

1116

1114

605

1028

880

829

622

161

138

840

830

868

768

843

884

933

970

280

704

374

428

1123

991

708

429

431

282

430

426

540

427

712

375

281

681

383

688

1100 425

1082

785

680

378

376

380

381

379

291 377

866

72

142

141

68

71

70 823

978

835

1088

834

822

102 101

99

382

682

689

783

756

1111

221

594

211

220

224

759

571

720

651

722

214

591

401

1011

1136

975

225

589

910

625

219

898

721

223

213

719 642

742 218

498

212

1099

638

105

434

27

435

741

607

75

112

836

1113

833

422

727

24

113

114

23

249

612

468

252 936

167

74

555

253

826

1085

254

247

251

17 73

119

570

257

250

744

648

1102

673

1089

569

922

559 166

400

402

165

16

815

245

1095

703

477

14

217

710

700

384

668

244

308

246

697

170

597

171

111

256

454

587

466

616

453

452 353

329

348

652

767

755

565

352

351

328

346

340

326

1020

707

906

761 354

420

331 332

344

487

647

465

520

530

347

350

327

341

323

851

916

412

419

472

792

411

417

413

415

635

418

595

416

567

342

343

763

983

405

664 330

714 325

321

414

407

494

364

365

222

349

345

538

324 388

596 408

409

451

725

322

669

646

410

966

1004

307

1144

1130

304

306

305

303

103

859

572

69

216

467

15

731

1045

558 930

821

1105

550

46

1104

883

964

811

848

728

982

894

45

143

67

1017

860

675

994

173

576

196

806

469

255

248

716

471

76

470

549

1131

424

421

676

816

423

404

780

566

564

743

366

406

363

636

696

262

264

490

960

895

981

373

489

574

265

369

368

334

267

505

1127

266

543

263

506

492

542

371

115

117

370

372

491

488

493

42

333

39

850

1138

976

268

1019

259

258

261

940

38

41

1140

40

43

260

44

243

560 9

650

1118

12

81

8

723

7

10

83

1115

653

1141

781

1001

758

765

1021

738 797

643

30

80

11

1125

627

84

50

82

29

87

503

88

699

772

877

670

803

180

13

85

86

557

151

927

286 285

1076

362

611

278

239

237

1083

665

634

277

360

150

149

655

357

810

528

355

690

361 709

873

155 156

442

745

618

289

827

288

283

287

279

367

746

284

236

356

729

1122

235

547

739

238

359

546

154

1135

358

499

153

1005

604

820

609

509 152

771

(a) Dartmouth, apenas arestas sociais.

701

724

1031

273

351

625

99

416

721

815

759

417

498

671

299

651

487

656

928

297

683

295

630

344

554

1012

464

463

717

390

874

3

684

1018

296

298

517

691

860

813

18

1106

236

568

226

442

516

341

1010

536

687

406

763

460

841

635

743

328

458

345

466

465

389

462

343

403

736

798

461

459

623

647

720

761

353

588

1072 796

307

705

42

1111

873

361

2

621

420

356

515

512

1083

493

359

4

526

332

530

119

714

669

327

101

1100

166

340

283 709

1130

445

421

693

927

567

248

159

157

149

286

1086

290

678

66

153

510 1122

739

547

1140

289

227

150

156

358

816

20

151

154

774

745

525

1142

355

518

827 760

360 620

820

609

674

846

619

499 229

237

65

0

424

288

21

773

586

843

279

362

155

856

235

152 746

1076

618

771

655

598

19

285

1022

1067

509

601 600

1005

777

239

22

929

822

776

423

834

209

710

165

141

105

112

337

114

102

606

528

354

557

722

806

467

349

511

762

70

45

916

469

898

778 978

786

308

539

707

826

597

716

276

228

330

936

558

1045

113

756

527

966

74

453

482

649

238

1017

1066

728

793

247

72

305

275

331

479

470

109

75

142

524

912 7

775

15

489

727

96

123

732

810

1095

438

673

741

253

1085

787

751

107

106

103

385

384

52

208

484

24

1119

507

648

994

697

211

922

418

23

146

28

480

1084

400

1102

836

473

339

71

391

570

478

54

256

546

456

252

731

636

859

254

59

86

257

171

249

785

1080

244

734

865

605 133

892 1068

1058

1028

831

429

993

1090

899

1063

1077

1065

1109

858

918

970

817

1107

987

962

925

457

144

690

508

637

604

269

1136

996

917

1094

884

534

869

932

838

891

823 998

1046

814

134

128

769

750

801

631

839

946

116

887

110

624 840

37

537

491

967

592

196

1110

503

531

835

975

1032

872

861

535

829

1024

876

132

488

504

986

857

561

765

749

378

495

982

976

629

1123

1089

1099

521

610

603

563

501

205

1062

694

556

807

569

434

638

58

757

387

562

612

139

639

335

541 496

317

550

336

681

108

292

98

94

399

97

935

443

27

306

60

481

485

440

187

404

910

326

915

325

321

322

538

983

652

851

407

642

725

405

559

67

419

303

408

451

410

472

616

347

664

596

494

348

767

364

329

906

1117 878

792

274

346

555 595

700

607

755

634

255

414

415

412

448

271

657

780

594

363

422

272

365

323

350

393

1030

733

641

91

392

402

475

1137

471

587

148

811

575

1104

885

217

591

53

990

599

1105

14

848

675 394

964

628 1113

718

185

68

224

455

666

210

577

100

486

115

46

30

313

842

221

744

17

726

314

16

218

57

867

703

1144

268

571

223

304

216

76

468

572

219

719

682

452

409

220

633

225

589

883

1020

930

388

56

143

413

89

26

824

646

251

477

277

73 454

366

222

566

324

742

213

214

212

520

411

352

668 342

564

565

611

665

549

357

287

1135

523

492

1088

847

723

188

371

1097

370

1082

617 202

602

11

853

737

124

802

177

740

13

83

104

198

92

84

88

401

1143

1127

372

650

121

614

658

627

653

201

643

713

126

730

808

991

543

791

476

293

82

574

560

140

376

1115

1125

425

50

699

670

505

1138

180

437

318

483

316

85

9

118

1141

55 552

1103

615

147

551

250

95

386

960 206

544

90

395

301

659

397

645

513

519

441

432

398

866

25

182

553

184

593

338

69

167

334

833

545 770 782

1004

809

170

111

748

474

738

533

1051

789

1000

396

300

433

125 1121

490

145

877

315 310 436 10

181

62

175

514

640

679

958

174

532

895

189

246

870 93

294

186

711

81

12

319

781

207

183

117

804

573

435

753

302

51

497

1049

1064

965

1059

989

1044

889

1073 772

1120

1001

576

127

281

33

36

178

449

1041

1091

1023

1055

64

548

685

47

172

803 179

758

173

522

821

35

122

204

291

80

309

29

500

312

797

1027

1101

686

161 578

1124

138

1050 933

735 963

1002

1112

768

954

914

864

949

1048

921 1060

980

913

1006

1079

974

1043

34

1081

799

31

897

950

920

862

937

902

903

901

948

945

1042

908

953

995

752

1016

1014 969

896

941

1038

863

1040

959

905

1053 934

977 926

1056

855

875

160

832

952

911

931

704

837

1037

909

947

1116

48

956 957

794

886 779

951

1092

1128

282

381

938 1008

698

1093

919

1096 1052

215

1015

428

1108

168

1025

939

1034

879

942

971

1036

979

608

232

695

973

706

1009

944

871

242

662

692

747

1134

968

1114 880

795

1057

812

961

1075

907

1039

1069

924

1035

985

893

992

278

644

788

367

169

284

1

890

529

136

203

582

626

231

622

805

77

888

135

63

613

197

240

320

191

176

32

819 1070

999

923

130

590

881

234

129

854

280

955

579

677

131

195

199

192

194

654

689

766

430

540

49

230

702

828

729 5

6

200

193

667

818

988

243

38

41

260

261

44

259

43

333

368

369

266

542

267

373

981

708 632

754

688

379

377

245

40

87

663

8

1021

120

894

262

263

264

506

265

1071

997

1087

882

849

233

1033 1118

783

844

825

972

79

764

427

61

1047

852

830

450 715

1133

190

78

900

241

1061

784

712

158

383

426

375

984

904

660

1029

1013

1054

1074

1007 800

137

1078

1003

868

164

580

584

585

845

672

374 311

1026

162

676

382

163

583

431

380

1098

1139

1126

1132

(b) Dartmouth, apenas arestas aleatorias.

1957

1844

2763

2791

1574

3239

2280

72

2749

935

933

1331

2691

997

1358

101

3095

603

2932

299

2232

208

612

1743

2269

989

368

743

1233

2221

2720

1654

2332

609 748 623

2058

1698

2322

3146

2670

736

2927

1272

3174 2105

1420

782

735

2146

508

2139

2314

2342

1177

2824

626

1720

46

1416

2558

689

852

3300

3192 2717

2219

2615

1980

2946

2344

1279

863

333

1855

1880

1870

1453

2727

2938

126

3155

702

1495

2311 1624

962

2192

2654

1634

2470

266

2346

2109

2407

100

64

1322

527 1579 1714

1191

2801

455 574 858

1721 392 2100

2017

1652

3221

1913

3201

687

199

304 2456

118

1059 2222 2178 1461

300 964

140

2571

1598

1405

2491

2505

2187

2353

1366

2273 1638

2695

1206 1512

137

1812

335

3079

1078

1468

2118

727

567

3168

1338 838

595

913

1920

1798

2768 2237

1269

1204

543

1645

1131

1240

2601

2416

2802

1232 1639

1681 2229

797 330

1552 2339

454

544

29

532

1418

877

1452

622

436

209

189

2398

1780

2019

468 1556

1063

1069

1401

2618

1303

1783

491 301 705 1505 791

977

422

1767

3290 1262

2753

144

906

2573

943

424

1061

1588

2617

2608

2641 3220

2486

2645

2837

3022

2566

2622

3026

2861

3020

3326

3048

2462

2599

2646

3049

2890

2846

3274

2779

2624

2731

2643 2511

2271

3225

2474 2591

2469 3045

2421 2600 3118 2291

2517 2015

2755

660

2506

3023

2542

2394

2449

2620

2924

1316

3061 1617

2335

3257

2943

2499

672

2451

2688

632 1127 1380

2760 36

2185

825 2466

2404

1144

1371

313

738

1977

98

3199

3139

1521 294

221

1417

2026

2640

165

3033

3030

2704

191

2310

41

1566

89

3147

2043

369

419

230

161

2548

2005

1606

241

2553

1424

3038

1421

3035

195

2308

693

512

1528

1640

2297

249

61

262

190

112

1595

1597

1155 1646

1031

248

233

178

776

179

270

243

453

2188

699

222

310

182

207

80

1094

395 338

961

231

305

187

169

88

49

47

434

228

240

1276

524

1117 594

471

255

200

344

439 627

376

549

3101

2794

3040

2186

879

104 572

3

3161

2003

1708

197 244 430 205 2313 678

213 1087

146

3328

357

744

1526

1695

2088

212

2340

888

882

2177

1842

164

278

1109

3254

2714

1205

2703

2556

1474

1581

513

17

289

789

425

2809 1163

68

1118

996

2272

731

826

1367

1949

749

785

288

183

1975

834

1231

242

1565

447

1707

821

119

820

2540

483

553

120

86

216

1744

1500

2533

2662

1413

1332

927

3298

2108

3047

2663

1572

3013 2424

3262

857

2987

2999

3010

1443

1665

733

606 463

535

815

1036 1157

1089

1501 3003

745

3001

75

34

1459

2525

2623

1503

1961 1170

6

1054

2953

2443

2633

354

1692

2412 1442

1312

1529 1043

309 625

1018

1375 1988

824

2045 1916

327

11

185

487

1524

1360

986

2166

74

682

1123

1469

786

999

2877

1702

2242

415

1140

505

1264

1458

437

28

110

2018

1487

924

2770

1093

1066

940

779

521

510

947

1482

432

793

957 1029

551

323

176

175

272

1562

790

399

285

343

223

441

365

367

1723

1856

1245

2722

167

2427

2428

166

919

30

763

2711

2376

1466 220

171

254

2054

1594

3275

459

1092

284

898

1867

1713

1476

671

787

251

819

162

315

275

177

163

122

552

22

2679

2825 2436

1667

976

855

186

582

269

1134

451 805

770

253 628

925

692

650

351

764

2836

2419

194

180

1055

81

136

38

1686

716

1457

250

257

1992

316

1800

1212 2694

2060

1086

714

531

1357

1208

1364

2510

658

60

469

1971

3164

2876

1690

1886

1968

792

1185

1982

739

2686

752

2742 237

1281 109

3151

2160

746

1688

2176

2702

1786

2414

1573

1238

2158

3098 1415

1921

235

2454

350

571

1857

1111

2546

44

287

125

76

2240

3229

332

379

1467

73

1689

1629 1954

605

1308

1859

2198

62

1995

2175

2588

157

423

1610

717 590

2067

429

2357

2741

1372

721 1486 1966

1700

638

1869 449 1591

818

474

558

715 3067

3059

1017

386

418

1483

370

3066

1580

2537

509 1154

1171

1676

2145

830

766

1128

701 1863 116

92 2164

489

633

968

466

411

283

586

2211

329

2258

1771

26

556

769

448

616

475

476

550

557

1541

1030

1625 1903

1558 2216

822

1815

2682

636

87

2733

21

538

2255 659

1560

591

433 3191

2151

1736 599

1846

457

1551

795

1600

2114

1737

3271

2248

1781

2583

2147

1077

66

35

1599 1589

111

2246

1257

1026

2665 2534

2773

1909 1039

1778

1167

1411 12

2805

1711

3142 3044

2382

849

2609

3323

1050

1289 1519

1235

1802

890

67

2157

1922

2631

2568

1724

1823

2011

2180 2886

14

1429

1307

2965

1441

836 2501

794

2341 3042

477

1035

2153 2820 1549 515

2205 502

91

15 45

2199

2816

1819

1718 1587

1001

1535

1311

1361

615

563

1745

2277 573

413 1825

27

372 880

20

486 1192

2182 1007

1943

576 2007

1794

1290

1627 1125

2368 2041

59

583

2184

1345

1201

732

651

2206

864

584

559

467 318 494

1068 480 761

640

1182 1941

3039

2563 1918

2022

1399

2765 1475

2354 1145

775

1927

321

1729 1972

1313

649

2610

2387

985

3093

1110

1097

2476

2074

2315

2831

2161

1013

2484

982

2715

1656

892

1162

1592

579

1090

2541

2396

2539

1946

1248

2477

2448

2307

617

1765

296

598

2226 2423

967

2165

1673

1604

1833

1214

1083

1278 1801

2266

2204

2810

561

1928

2916

2156

2068

63

412

174

404

154

43

495

1684

96

24

93

2508

1522

2103

662

1009

1058

2333

1492

1864

926

2411

131

1423

428

2200

2384

155

1872

1838

952

2459

331

1448

2854

1188

2135

2144

2413

2142

1964

2128

641

2381

2936

2883

2956

1106

2389

1359

1014

2130

1141

1075

1386

1193

2947

1960 2570

2958

555

2168

1330

2197

2127

2046

2933

2038

674

1304

2149

2124

1893

2129

2123

2143

2140

2596

2172

866 359 1934

1398

2195

807

1348

2504 2872

1666

1843

751

1082

931

647 2669

1575

1456

1218 3253

2122

1194

2955

1085 2793

1861

1365

2562

2671

2942

1260

1255

1306

710

478

259

1734 724 1300

1518 1028

722

417 655

473

683

796

482

1948

712

2183

256

2355

440

410

393

2730

1787

1756

1929

2133

2136 937

920

380

3159

1582 1319

1805 2241

2085

613

865

3009

2667

1091

2406

2509

1347

2082

1152

908

637

1403

1166

1209

2473

1478

1496

2159

3008

580

5

1649

1422

2475

1199 1247

2481

2115

1567

1173

901

31

973

2244

1310

1407

152

108

85

40

1175

1203

2008

2529

1156

138

511 1242

345

903

2032 1003

2327

2393

2528

1445

2131

885

917

1284

2080

1295

2644

1228

2594

2464

2660

2461

2993

3215

414

3127

814

3017

2619

274

4

756

1385

932

2099

496

7

23

1828 1342

737

8

2445

547

1784

690

2057

974

2155

2062

2249

485

0

2101

1465

1917

1317

2243

402

90

1224

1178

1547

37

484

696

334

1987

2059 2173

295

2440

39

1340

2997

3324 891 2485

503 1138

2630

384

123

1396

2030

1611

1648

1382

1532

657

517

445

1

1438

1999

642

685

168

147

42

2441

1694

1211 2250 1602

497 2371 631

1292

2084

1697

1258

566

954

409

2744

58

1570

998 1774

1024

1491

2453

498

3099

704

1101

709

980 1822

1412

667

827

1098

2560 1626 860 630

57

1564

1033

1165

1374

1391

665

2835 645

107

377

948

2437

2593

604

117

656

1677

2106

2004

1287

545

133

867

156

1766

355

720 1027

546

1220

540

406

853

1768

1104

669

809

646

397

124

1910

2572

141

1042 1408

856

148

777

353

1642

3264

383

504

499

1742

1381

1759

2336

452

969 729

2010 1631 1088

239

2614

2117

2433

944

1791 2065

2097

2664

1135

492

1410 536

734

2904

83

774

1222

1959

341

2

2612

1011

261

664

525

132

130

224

481

1911

340

442

1363

1860

2520

1571

2586 2970

1353 3321

2626

373

3278 3265

3006

3267

3249

2692

2463

2163

1636

1507

1952 992

2490

1389

1195 2512

3060

2098

1506

1168

530

1060

444

2286

1433

2028

2661

2569

361 258

298

48

1628

211

2425

2488

1354

2928

1159

2390

2112

97

2483

2338

366

773

2299

611

3178

868

3031

3072

956

614

281

71

1261

887

1449

1866

1836

844

1378

2069

307

747

1270

2228

1888

1733

2973

878

883

479

1032

1234

263

922

2190

828

942

2326

2487

909

1847

587

1277

2110

1712

1022

1393

1709

2120

1164

918

520

621

113

938

348

841

2212

955

3295

1932

2306

1440

1333

416 2094

1368

2207

1739

2978

2364

1254

2137

629

1703

897

1661

539

2035

2132

2863

3089

634

1728

3325

1273 388

804

570

970

385

1531

564

2959

1935

82

2941 762

577

958

829

128

2444

1174

2281

1427

1016

1455

2330

1142

912

303

1064

2637

946

236

1970

1875

2265

2312

601

145

2536

2107

1008

1883

352

3133

2225

2154 99 2460

2701

2037 160

106

2446

979

279

930

1006

1731

1062

181 308

1291

389

70

2979

934 1280 2447 2235 2468 2827

1978

881

2288

1683

282

2104

431

1015

54

198

1630

936

850

2693

578

3136

2685

899

3214

2697

2403

2684

2747

3158

3186

2975

3170

2713

2874

2743

2465

2402

2764

2804

688

1122

1871

202

2590

1722

1717

387

2095

2494

1578 1239

1298

320

1051

534

2089

2860

1848

297

2031

3113

1216

1912

192

1147

1005 2193

1658

723

127

378

1763

1326

1561

1010

2611

3110

1197

3107

3109

(c) USC, apenas arestas sociais.

1920

2070 2833

3168

1996

1838

2373 2194

2440

1090

2043

1461 631

1822

1688

1918

2226

2074

2573

1855

1792

969

1968

2113

2817

2818

2515

3063

798

951

3122

1821

2036

967

1848

1834

1868

1878

788

784

711

2073

2015

1231

1172

1283 1114

1063

1827

2266

1862

1814

1989 1204

1901

1282

2736

2017

2746

2294

2743

3190

2713

2757

2732

3087

3110

3158

2403

3107

2747

2925

2693

2874

2697

3248

2764

2864

2465

2689

3065

3113

2685

2975

3170

3106

1428

2293

1539

2092

3268

3029

2214

3186

2684

2390

2690

2372

3180

3049 2086 2315

2431 3231

2338

3003

2300

2506

2112

2089

2433

2477 2446

2161

2610

2521

2654

2482

1876

2321

2097

2834

2769

2447

2286

3019

2287

3257

2607

2621

2797

2661

2648

2957

2641

2616

3206

2298 2458

2417

2558

2598

2306 2688

3221

2745

2165

1931

2579

2448

2273

3182

3259

3017

2569

2479

3033

3148

3313

3294

2588

1921

2101

2152

2737

1983

2924

2453

2941

2331

2499

2657

2735

2985

3290

3163

2855

2003

3002

2760

2109

2173

2837

2568

2322

2702

2871

2248

3155

2744

2594

2642

2794

2541

2061

3032

3296

3255

2954

3261 899

2013

3136

3109

3229

2602

3305

2334

2848

3079

3237

3244

2158

2878

3041

2854

2452

2466

2347

2496

2664

2788

2632

2318

2950

2572

2100

2155

2411

2192

268

1695

2019

2012

3310

2320

2885

2005

3241

2056

2261

2077

2222

2028

2487

1889

2994

2105

2426

1554

1062

829

587

2055

2212

1008

1866

661

918

841

909

1016

520

307

1370

938

930

2253

577

1836

2979

1727

1164

2190

2786

955

1005

946

828

293

762

747

1233

1675

2712

2528

782

2256

1449

2186

2225

2892

348

2312

1277

263

1630

2029

2875

554

581

2337

881

2402

1459

1291

614

145

1669

114

3001

3016

1740

1995

1080

2814

2586

884

147

1230

2843

2048

2720

2603

921

493

548

568

3320

1463

1951

995

765

1749

2707

1274

181

129

282

1888

922

878

1970

837

1978

198

308

936

1427

621

1234

1437

281

1052

472

979

1273

1633

1875 236

2047

526

2980

2650

3243

2634

2546

1885

1498

2804

3069

1430

2590

3043

2120

2807

3133

2656

3153

2024

1897

3057

3117

1938

3249

3089

3225

2349

2999

2997

2421

3108

3298

2220

3120

2267

1737

2187

3262

928

3094

2241

3219

3100

2635

3324

3023

1665

3005

3034

2599

3013

2407

2886

2481

2509

886

2249

1988

2443

3008

2053

3316

2291

3000

2406

3328

2542

2131

2646

2393

2865

2914

2498

1672

3278

3325 2091

2748

1680

1432 1185

1379

1341

758

314

2516 3053

1859

2881

3052

801

887

381

389

2619

2763

601

759

2104

1174

352

1561

2107

3147

3177

1733

2879

1902

942

2076

1133

688

1261

2495

1122

1450

507

387

113

1844

2288

2973

2536

1912

2636

2119 2922

379

3304

3086

2795

2490

2328

2485

3322

2459

1704

2627

632 2308

1516

2203

2507

2083

1812

1797

3081

1414

792

1216

910

388

1

1826

2341

2589

2460

1714

1748

962

1522

1325

802

662

1620

1853

2075

1388

2606

1999

2721

1159

1070

653

1147

742

804

1166

1864

1728 1399

1397

1301 2049

1617

1759

1439

1634 1073

874

660

2344

2658

2010 2295

903

1412

1652

1537

2078

1915

1967

2456

1248

1604

1336

2501 1946

1850

964

2350

1780

3211

1408

1626

981

1286

1338

1673

2335

2488

2425

1833

879

1383

1239

693

1534

2065

2217 1540

982 2004

1906

1356

794 148

1521

1508

1280 1381

1009

1088

1754

2505

2461

2032

1443

1195

3132 2826

3299 1823

3306 1811

3165

2512

1413

1317

1503

3317

1588 1050

1991

2609

2629

2849

2059

2645

3319

1916

1777

2964

3021

1616

1332 1832

2624

2566

2080

917

1849

1507

1611

1974

2006

1353 3210

3009

2116

1668 2494

3078

2822

3112

2987

1589

1504

2193

1203

3048

1709

1249

2095

944

1074 1013

1279

1956 905

860 2475

3022 2263

1593 2587

3137

279

3329

2209

1191 1831

783

57

3326 2832 1049

2429 1981

2640

839

707 1623

956

261

2778

1494

2970

2099

2464

1726

3025 975 3250

2270 2240

1512

718

340

273 215

1963

2868

2867

3031

2027

2400 2096

1674

1390

916

746

3239 1683

3058

1954

1870

2611

3297 2918

908

885 1429

2090

3093

1464

2310

3179

331

487

211

219

2265

2069

2444 2846

3020

816

1091

192

1112

780

673

1420

84

56

2034

1544

743

2812

102

1904

1355

2791

50

1583

1857

1344

1433

2093

1020

652

286

1153

1898

2696

358

1378

2575

157

1444

2110

2790

2921 2787

1015

2281

2221

902

252

3214

70

2678

2081

934

1046

1782

2289

872

2694

578

833 808

1764

1445

2779

479

840

2571

750

384

71

745

1199

2630 974

1942

1054

6

168

2998

3037

3044

2244

2115 2993 1670 2486

2644

1649

2600

3101

16

1393

2623

2617

2159

1465

1987 1422

1121

402

2463

3142

2633 3036

2346 2643

2469

973

1692

2731

2082

2327

3220

503

2062

414

1883

560

883

1693

1663

690

4

3060

685 1396

2030

90

3265

23

511 100

1284

932

2008

8 2442

1961

2409 2992

2659 2674

1984

1394

1346

907

3007

2296

2377 2784

2316

2234

876

2117

2476

2324

2574

2683

2480

1747

1573

52

2493

2401

1800

2585

1078

2340

2410

1619

2869

2384

2351

3311

2396

3209

1654

2655

1362

2001

1446 939

394

2468

428

247

33

2483

2454

2484

1791

1354

752

2563

2284

2759 2567

2274

2518 2535

725

2319

619

2470

2299

630 527

1097

2371

2404

2984

2839

3300

2762

2232

1556

2946

1058

2063 1315

2009

1614

2815 1765

1119

812

311

2752

1933

2503

2577

2102

2959

3121

2717

1253

1259

2593

2103

1980

3080

1645

1100

531

373

2162

2706

2753

2754

1935

2923

2680

2961

1440

3184

727

1592

2111

2755

2831

492 468

409

2547

679

612

3138

2810

3315

1555

3312

2228

564

1657

1887

2326

51

1509

1525 996

1087

2200

989

999

2514

1144

826

276

1609

1452

1212

1937

1146

1158

820

228

156

474

1787

1813

1335

1493

1751

201

1742

966 1278

598

2809

1453

1817

862

1460

2789

781

596

337

1177

1243 1879

1415

398

2439

2160

2272

2342

753

1131

2450

2990

2909

2526

1541

1094

540

209 1163

1232

2554

2238

149

2582

2178

2595

2561

1098

738

1947 1907 353 1165

1409 2620

1316

2250 1238

1637 2963

2539

2527

1371 667

645

1303

585

800

1258

1721

1184

333 1222

689

1225

328

1101

1032

1059

132

144

827

298

777

2938

877

892

491

304

118 2084

2264 462 1479

1711

1377

1886 1302

1913

2398

2307

2414

1229

1586

656

342

1424

1766

1287

1012

2392

1706

1040

789

694

926 12

3035

107

1497 2544

1423

2695 2614

1578

1227

1352

130

838

2715

709

665

1197 1211

672

427

1246

2219

2336 140

2835

664

1206

570

306

363 1656

121

675

2729

924

1262

1137

1143

778

618

1021

460

375

226

1307

2437

2524

2314

894

316

361

2771

319

1321

720

509

842

546

488

2428

2555

2910

589

2897

1140

2215

1308

357

848

1364

1786

2181

3039

3187

3226

3208

3040 2870

3205

2842

3115

3050

2227

3234

2189

2932

3256

3245

3150

3215

3091

3102

2847

1113

3083

2808

3271

2898

1923

3216

2147

2088

2303

1716

904

3240

2988

2917

851

728

1678

1213

2844

3129

2533

1778

2670

3323

2198

2969

1416

3167

1807

3197

1950

1884

3160

1559

1358

1489

2141

2896

3198

3263

3154

2625

3195

2231

1725

1936

2928

2740

3103

2904

2628

1992

1804

1628

1275

1455

2995

3277

2912

2758

2949

1808 1200

1198

1271

2500

2058 1694

3018

3264

3280

2014

2467

297

605

522

3174

2531

2841

3272

2781

3139

1596

2301

965

127

446

2278

3098

3004

3224

416

2927

2926

1743

1976

1081

1610

993

65

72

368

1570

1022

2218

3201

875

861

461

303

2637

1701

2492

1281

3178

723

2819

324

202

1932

2668

3099

2903

2060

3235

2705

2471

1086 3

2455

2775

3267

2965

470

2354

1618

1077

79

1965 3301

1746

2591

868

1653

66

970

1524

10

1651

2806

188

3126

1605

1760

1810

1047

77 1835

3152

1788

984 1650

2948

3071

1824

1612 2698

933

2174

895

2893 2782

349

105

1927

2108 1799

1781

1659

748

815

1909

1257

1039

610

2894 2920

1331

111 78

3119 3061

277 985

1491

2866

1802

1410

1644

3111

1874

2525

3171

1629

963

1533

230

2719

3164

3270 3279

408

3273

2251

2913

3161

945

1762

2880

831

203

101

1730

1564

3292

1590

3274

620

210

1201

1368 1260

1179

1079

1136

1071

1116

712

592

3172

3194

1708

3084

1529

1546

2631 287

258

2 170

2766

3276 3223

3114

2857

2860

3204

2175

1957 1333

2901

2905

1210

2329

2862

1149

1542

1789

960

1839

9

3212

2613

2224

2202

1323

2397

1615

2044

1712

2899

1803

3077

2930

3146

3125

873

1320

2765

2828

1919

1530

1779

2359

2907

1969

2723

1252

1757

1865 3027

3082

869

401

2478

2708

1523

2050

3157

3282

2534

3097

3318

1402

1395

347

3183

3232

772

2271

1895

2037

736

817

2179

3309

2662

2246

3321

3291 2230

1940

1816

1717

889

1467

2011

3010

1922

1643

1385

1517

1607

2424 2989

1425

1411

1941

2180

1809

2773 3047

2953

1796

2796

1343

3189

2157

735

2803

2233

1215

1608

246

1289

1613

1187

2665

1288

94

55

847

1715 2991

1099

929

1019

172

1990

1741

2686

1755

2777

1818

1250

2052

843

3045

3200

3202

2850

3072

3193

2040

1772

1719

1438 2840

2176

2146

2823

1690

69

1722

2856

3116

1698

2776

1696

935

3128

1095

1971

726

997

3143

2269

3140

2538

2792

1454

1309

914

2974

1943

1549

2543

2682

1830

2375 2550

1622

2944

2399

1894

1480

2889

2783

2863

3105

2793 2596

1801

2669

3246

597

2972

3141

2564

3014

2986

3230

2605

3307

2951

3247

1392

3095

1181

3134

1169

2438

1492

575

1647

2502

2939

3028

1840

2330

2584

2254

2639

2691

2827 562

2079

2087

1436

3269

3260

3327

3285

2983

1161

3185

2911

2940

2751

490

3156

1538

3295 2604

2513

1851

2000

2415

2039 2977

2388

3055

2902

1993

2960

2859

2976

1226

3123 1072

541

1142

1447

823

1997

3176

3314

2971

3074

3302

2908

1994

1986

1293

1272

1720

1264

1196

1120

888

542

3151

2982

2968

2302

1139

1270

988

859

1326

1048

2094

2931

2434

2317

1023

2576

1064

1732

2427 3238

1251

1221

754

593

3012 1084

1958

1103

3064

1928

2824

1220

2510

3266

421

3159

2942 1998

3284

2733

2996

1881

1171

1357

2376

1130 3253 1369

2671

1975 2967

950

450

3104

565

2540

915

2836

1487

1705

2770

2710

2888

2166

2728

2800

2374

682

222

2730

2734

1124

2339

2741

3236

2726

1601

1462

1499

2679

1577

420

1985

2681

2260

2223 1536

991

919

893

3073

3293

3124

1723

1269

1025

2170

3070

978 1154

386

624

633

845

796 646

557

556

24

26

14

291

676

2830

2436

2813

972

2802

2906

288

278

143

2811

2725

312

1528

2164

45

1846

2169

1083

283

515

761

1775

2441

346

2673

1205

771

1134 1476 767

323

269

253

1856

1552

2245

1686

1793

2242

787

1485 1867

1502

1681

757

351

207

178

627

986

716

770

543 940 1123

1744

512 521

819

790 763 382

1565

1490

365

434

1150 218

1585

1767 280

1470

223

166 19

240

177 925 730

220

1469

1223

785

764

167

2581

200

162

136 18

214

153

459 1770

325

1603 559

1010

626 513 1151

1739 284

1852 1580

670

2756

1736

1584

552

1236

189

1595 704

853

2877 449

457

249 213

86

976

1640

1667

1482

779

805

663

681

532

301

232

582

505

1581

1055

1661 1002

793

205

176

171

88

705

425

2722 1562

422

285

1044 1017

1774

2592

1292

455

415

1031

371

2054

2716

634 1092

821

749

251

186

27

1785

795

1304

1700

751

448

46

1699

1794 629

2774

1056 1093

1348

937

1718

710

355 173

133

1125 489

2199

1014

880

2205

2675

659

502

506

15

971

2700

305

1646

216 183

1466

994

1117

2237

650

338 343

244

697

134

628

187

551

453 834 1707

439

786 1276

289

164

49 911

524

1930

588

961 1597

1155

1102

262

233

194

254

544

248 797

197

447

61

22

17

1900

1109

2391 2687

255 120

119

112

310

864

594

1067

250 692

362

2333

182

1639

344

508

315 29

1474 1750 430 169

395

190

30

367

2229

399

437 330

2257

2724

243

376

3051

504

647

391

616 47

433

576 1819

550

1768

1068

549

1966

406

110

93

1104

573

897 2958

1096

413

404 2504

1207

766

2156

43

2677

21

1815

724

615

528

1082 2285

1703 722

2277

638 1306 476

537

2523

1027 855

1451

2210

813 92

1925

1345

768

2489

3203

2405

2667

1506 1157

1242

1349

2491

523

423 1805 2652

1567

485

1380

1337

332

2549

1514

1442

1582 3030

1478

1426 516

139

3145

2311 2423

3175

3038

2026

2801

2548

294

458 469

2283

1340

1319

356 1599

1297

452

1400

3127

1391

5

108

1167 1152

1389

1244

2701 2449

1735

2025

1519

1053

1574 1880

390 703 431

321

2583

2676

3149

309

2551

3252

3162

3006

3118

2473

2051

1441

613

264

75

3068

2861

2845

2045

1305

857

3222 1314 3217

1006

1475

1089

1138

2622

1820

1347

3173 3075

900

206

2114

717

1041

2163

445

1806

2851

260

193

97

11 2474

2935

2767

2497

2663

1543

1758

2167

529

901

67 64

1641

2387 1572

2064

1350

923

639

31

2520 1435

2276

2559

625 949

54

2517 2332 702

2560

3011 1401

1373 2739

1952 2353 3289

1178 2876 2007

2882

2873

383

296

760

595

265

237

854

13

2612

1110

2259

2890

680 567

161 756

1403

2821

2275

385 403

536

604

1188

803

335

160

117

954 89

913 377

525

602

852

1513 1899

1145 836

1495

39

225

128

106

152

1003

185

569

1026

1545 1312

1658

274

3026 2323

2445

1829

1532

1977

1837 2649

1038

3024

2660

1689

1784 1598

775

339

1407

1148

1173

850

1606

2692

1235

354

607

501

1501

2071

1510

1873

419

271 204

125

865

334 196

1636

327

606

115

1366

123

42

400

234

517

103

2638

1710 2085 2750

2098

2647 3308

1224

85

7

2280

2626

1406

1790

2557 2472

2412

2727

870

1917

1329

484

927

657

1209

1328

1648

1043

290

2653

2666

2282 2057

2738

2394

1135

1448

1310

1322

580

1496

1571

1342

1061

34

138

814

642

1828

2462

1247 1168

1175

2243

547

2511 1860

2608

3169

2508 2106

1738

2615 1488

863

2451

980

729

687 392

990

1024 1677

1602

740

313

755

1959

2235

1240

1911

600

82

1854 1697

1638

1783

700

1219

941

579

608

295

48

1107

1060 1576

719

1160

302

300

235

199

739

1256

846

1374

1294

952 1642

637

499

464

341

948 424

2530

58

890

871

1845

1186

320

456

1687

1624

1033

221

658

774

83

1731 1579

1753

184

345

611

906 530

643

1000

444

481

266

292

239

2805

1034 191

1872

1162

1042

1156 2118

714

126

131

1434

2262

695

2529

2601

2742

1018

992

0

155

1892

856

1375

1382

824

737

496

350

135

37 32

1763

1531

1547

1982

1405

374

366

40

1566

958 1527

1419

95

41

62

497

396

195

648

1228

617

369

811

2699

317

1170

1295 1296

1011

426

844

2072

158

137 2252

407 953

2553

1847

36

1417

1127

1569

1111

603

1339

463

590

238

810

1632 744

1515

1036

1724

1655 734

53

644

696

2022

1526

609

1334

1511

943

733

891

2021

1360

1318

2201

1631

1129 623 73

1051

1858

1421

1069

98

571

1108

572

1237

535

241

378

227

104

109

912

773

835

1267

99

76

212

44

1635

60

519

635

35

3144

3275 2952

1842

2798

698

465

38

2419

1351 3233

2919

799

1557

1841

1939

2709

2711

2703 2247

1245

957 731

179

159

1118 671

1500

3130

2313

1713 2188 3056

1484

1702

1481

2780 242

81

699

622

713

1115

432

122

518

977

471

2366

2820

1594

2768

2297 1029

322

326

272

275

180

68

441

553

1926

2718

947 1066

405

146

74

231

2714

510 1263

483

806

3166

165

175

80

270

245

436

163

454

1776

1520

1457

451

2305

2068

3218

2134

1404

1882

1505

2128

2825

3096

3254

1568 2556

150

3085

2532

2364 2381

2023

2362

2367

2145

1662

1468

1684

2041

2545

1685

2168

2358

1771

2042

3196

1682

2153

2413

2020

2046

1729

1587

1591

1550

1483

2420

2430

2292

708

1660

2408

3227

1979

2522

2570

1908

1386

1290

63

1300

1625

1773

1214

2378 1945

2355

2416

2129

442

359

477

2389

2552

2916

1456

2132

495

558

142

514

2915

2872

1734 1486

1863 1972

2900

478

410

677

641

2140

1035

1182

2206

2195

1471

2204

2360

2365

2361

1387

2457

2182

2139

3066 3191

3062

2672

649

2144 2962

2123

818

2356

2290

2124

2385

2236

2207

1105

2197

1190

1065

849

1798 3059

791

674

1893

1535

1518

2191

1691

1910

2211

2149

2184

2172 2136

2858

1217

776

2357

2067 3287

1141

684

2137

2138

898 983

678

586 1752 1372

2258

715

1106

1756

769

1028

534

822

959

1361

1255 2213

435

256

1176

669

2196

2945

2216

1929

2143

91

1266

3258

1890

3207

224

654

666 2018

2368

1365

1924

2761

591

533

1676

2126

2130

920

498

116

20

2933

1953

686

1359

561

668 2268

2936

2150

3281

2978

2852

2379

2369

2580

1202 87

2125

1128

1948

2121 3188

584 866

741

257

259

1795

2183

2947

1030

96

2386

1007

2135 1903

538

1241

1057

1085

1076

2151

732

1254

1563

683

473

418

2537

1268

706

807

691 640

574

563

545

1664

1327

1313

2562

1045 867

809

494

429

393

858 2309 1311

583

482 412

59

1001

1761

1472

1621

2772

1194 1132

3135

1180

2816

1964

1671

896

931

825

417

1363 1679

1285

1398

1330

636

1192

721

1560

1553 1183

1551

467

599

566 1193

2304

655

1869

1745

466 2038

486

2016

1575

1367

1558

217

154

28

1324

1189

141 998

1548

1418

443

438

1934

1126 882

1666

3090

1949

555

1627

2031

1825

1037

1004

1843

830

440 397

174

25

2884

1861

3067

968

480

1075

299

370

832

1208

2133

475

364

651

1600

318

329

208

701

124

539

2171

2704

2035

2325

2122

1914 2002 2883 2343 2929

2519

2597

360

2565

2853 2943

2578

2981

2154

2255

2380

1891

1376

2966

2799

2348

2185

1905

2177

1458

2066

2033

2352 2618

2749

3228

3199

3076

2395

2651

1944 3213

2934

3042

2345

2891

2887

1769

3303

3192

1962

3131

3181

3054

1431

3251

2895

3242

3092

2838

1473

336

229

267

1477

2370

2208

3046

2363

3283

2785

2432

1973

2142

2279

380 1955

1265

987 1877

2937

3015

3288

2956

1896

1298

2239

372

3286

2435

2383 2382

2955

1960

1384

1218

2148

1299 3088

2829

2422

2127 2418 500

411

151

(d) USC, apenas arestas aleatorias.

Figure 4. Retratos das redes de Dartmouth e USC depois de 1 seman a de interac oes,considerando apenas arestas sociais ou aleat orias.

E importante tambem analisar o comportamento do coeficiente de agrupamentodas redes quando elas contem somente arestas de um determinado tipo, uma vez que

1Esses valores foram definidos manualmente, visando garantir tanto umabaixa taxa de falso positivos quanto umaquantidade significativa de arestas sociais.

Page 10: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

elas indicam precisamente se uma redee classificada como social ou aleatoria. A maiordiferenca entre os valorese verificada na rede de Dartmouth, como pode ser observadonas figuras 5-a e 5-b. Quando sao consideradas apenas arestas sociais, a diferenca en-tre os coeficientes de agrupamentoe constante ee maior que uma ordem de magnitude.Por outro lado, quando sao consideradas apenas as arestas aleatorias, os coeficientes deagrupamento sao semelhantes e evoluem juntos. Para a rede da USC, como pode serobservado nas figuras 5-a e 5-b, a diferenca entre os coeficientes de agrupamento aumen-tou quando se considera apenas as arestas sociais em comparacao com o cenario quandoa rede contem todas as arestas. Por outro lado, quando se considera apenas as arestasaleatorias, a diferenca diminuiu ao longo do tempo, com os valores se tornando seme-lhantes.

0 10 20 30 400

0.2

0.4

0.6

0.8

time (days)

Clu

ster

ing

Coe

ffici

ent

realrandom

(a) Dartmouth, apenasarestas sociais.

0 10 20 30 400

0.2

0.4

0.6

0.8

time (days)

Clu

ster

ing

Coe

ffici

ent

realrandom

(b) Dartmouth, apenasarestas aleatorias.

0 10 20 30 400

0.2

0.4

0.6

0.8

time (days)

Clu

ster

ing

Coe

ffici

ent

realrandom

(c) USC, apenas arestas so-ciais.

0 10 20 30 400

0.2

0.4

0.6

0.8

time (days)

Clu

ster

ing

Coe

ffici

ent

realrandom

(d) USC, apenas arestasaleatorias.

Figure 5. Evoluc ao do coeficiente de aglomerac ao das redes de Dartmouth e USC Gse suas correspondentes redes aleat orias G

Rs quando s ao consideradas apenas arestassociais ou aleat orias.

4.2. Predicao

Dado que as relacoes sociais sao regulares e se repetem com o tempo,e interessante veri-ficar se as arestas que classificamos como sociais na base de treino aparecem tambem nabase de teste. As figuras 6-a e 6-c mostram a porcentagem de arestas que foram classi-ficadas como sociais e aleatorias no nosso conjunto de treino para um dado valor deTw

que tambem aparece no nosso conjunto de teste. Pode-se observar quea medida que oparametro limiteTw aumenta, tambem aumenta a probabilidade de uma aresta classifi-cada como social aparecer tambem no conjunto de teste. Issoe explicado pelo fato dequea medida queTw aumenta, a persistencia mınima de arestas sociais tambem aumenta,tornando-as mais propensas a aparecer no futuro. No entanto, a taxa de aparecimento dearestas sociais diminui para a rede USC quandoTw > 0, 65, pois ha poucas arestas narede com persistencia superior a este valor (≈ 0.1%, ver figura 2), o que torna a analisetendenciosa para essas arestas. Por outro lado, para a rede de Dartmouth, quandoTw

aumenta, mais arestas sociais sao erroneamente classificados como aleatorias, o que au-menta a probabilidade de uma aresta classificada como aleatoria aparecer no futuro.

Al em disso, na Figura 6-b e 6-d,e mostrado o atraso medio que as arestas classi-ficadas como sociais e como aleatorios levam para aparecer no conjunto de teste. Comoesperado, as arestas sociais geralmente aparecem antes queas arestas aleatorias. Umavez que as arestas sociais representam encontros regularese de rotina, espera-se que esseencontro ocorra muitas vezes durante a semana, enquanto encontros aleatorios devem serdistribuıdos uniformemente ao longo do tempo. Mais uma vez,a medida que o parametrolimite Tw aumenta, mais arestas sociais sao erroneamente classificados como aleatorias,fazendo com que o atraso medio das arestas aleatorias diminua na rede de Dartmouth.

Page 11: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

0 0.5 10

20

40

60

80

threshold Tw

Acc

urac

y (%

)

social edgesrandom edges

(a) Dartmouth,% of edgesthat appear.

0 0.5 14

5

6

7

8

threshold Tw

dela

y to

app

ear

(h)

social edgesrandom edges

(b) Dartmouth, median de-lay.

0 0.5 10

20

40

60

80

threshold Tw

Acc

urac

y (%

)

social edgesrandom edges

(c) USC,% of edges that ap-pear.

0 0.5 14

6

8

10

12

threshold Tw

dela

y to

app

ear

(h)

social edgesrandom edges

(d) USC, median delay.

Figure 6. O impacto do par ametro limite Tw. (coluna da esquerda) O percentual de arestasque foram classificadas como sociais e como aleat orias que aparecem tamb em na basede testes (coluna da direita). A mediana do atraso (em horas) para as arestas aparecerem.

Dataset Tw Social edges Random edges

Dartmouth 0.2 57378(48%) 118344(52%)USC 0.1 210790(20%) 1077202(80%)

Table 2. Par ametros da disseminac ao de dados.

4.3. Disseminacao de Dados

Dadas todas as evidencias de que nossa classificacao foi eficaz,e possıvel monitorar asredes a partir da sua rede social, que desconsidera as conexoes aleatorias. O administradorde uma operadora de telefonia movel, por exemplo, pode usar esse metodo para detectar asrelacoes sociais de seus clientes e, portanto, usar esse conhecimento para disseminar umainformacao prestada na rede sem a utilizacao da infraestrutura da rede, como propostoem [Daly and Haahr 2007, Hossmann et al. 2009, Katsaros et al.2010].

Nessa direcao, observa-se, entao, como a informacao se dissemina na rede quando(i) todas as arestas estao disponıveis, (ii) quando apenas arestas sociais estao disponıveis,e (iii) quando apenas arestas aleatorias estao disponıveis na rede. Mais uma vez, para ospontos (ii) e (iii), para a rede de Dartmouth,Tw = 0, 2, e para a rede USC,Tw = 0, 1. Onumero de arestas classificadas como sociais e como aleatorias por conjunto de dadosemostrada na Tabela 4.3.

Uma inundacao simples do tipounicaste realizada na rede usando fontes dife-rentes e, em seguida, observa-se o tempo de atraso para que osnos sejam atingidos peladisseminacao de dados. Mais especificamente,e escolhido um no aleatorio ns para ser ono de origem, ou seja, o no que vai comecar a divulgar a informacao. Depois, define-seo tempo inicialt0 como o momento do primeiro contato entrens e o primeiro no que vaireceber a informacaoni. O atrasoli do no i e definido como0, poise o primeiro contato.Apos a simulacao, a mediana dos atrasosl e calculada para todos os atrasoslj para todosos nosnj que foram atingidos pela inundacao.

A figura 7 mostra a media das medianas dos atrasosl e seus respectivos intervalosde confianca de95%. Em primeiro lugar, observe como sao diferentes os impactos dasarestas sociais e aleatorias em ambas as redes. Enquanto na rede Dartmouth as arestassociais, que representam48% das arestas, sao capazes de propagar informacao tao bemquanto quando se tem todas as arestas, na rede USC as arestas sociais, que represen-tam20% das arestas, tem um desempenho significativamente pior. Isso acontece devidoas caracterısticas da distribuicao da persistencia das arestas de cada rede. Enquanto narede Dartmouth a persistencia das arestase quase uniformemente distribuıda, na rede

Page 12: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

USC a distribuicaoe quase exponencial, com as arestas de baixa persistencia (ou arestasaleatorias) dominando a distribuicao.

Outro fato interessantee que, na rede USC, o desempenho da disseminacaoquando se usa apenas arestas aleatorias e melhor que quando se usa todas as arestas.Isso acontece devidoa forma que se calculat0, quee calculado apenas quando o primeirocontato ocorre. Assim, quando o primeiro contatoe um contato social, a difusao se es-palha apenas na comunidade em que os nos estao inseridos (por exemplo, um laboratorioou uma sala de aula).E sabido que as pessoas ficam uma quantidade significativa detempo nesses ambientes antes de sair, o que aumenta o atraso.Por outro lado, quando oprimeiro contatoe um contato aleatorio, isso provavelmente significa que ambos os nosestao emareas de transicao ouareas povoadas, como restaurantes ou arenas esportivas, oque leva a uma rapida disseminacao entre os indivıduos de diferentes comunidades.

Dartmouth USC0

50

100

150

200

250

med

ian

dela

y (h

)

allsocialrandom

Figure 7. Comportamento da disseminac ao de dados quando se usa (1) todas as arestas,(2) apenas arestas sociais e (3) apenas arestas aleat orias.

Essas observacoes sao fundamentais quando se quer divulgar uma informacaoprestada em uma rede sem o uso de um controle central, tais como a infraestrutura 3Gdas operadoras moveis. O projeto de uma solucao de disseminacao deve ser diferente edependente do cenario analisado. Na rede de Dartmouth, por exemplo, pode-se usar so-mente arestas sociais para disseminar informacoes, economizando memoria (apenas48%das arestas sao sociais quandoTw = 0, 2) e recursos de processamento (o calculo de cami-nhos em grafos menores/esparsose mais rapido). Por outro lado, uma vez que foi obser-vado que a mobilidade na rede USCe alta e arestas aleatorias divulgam informacoes maisrapidamente que as arestas sociais, entao pode-se projetar uma solucao de disseminacaocompletamentead hoc, com nos propagando informacoes de forma aleatoria em toda arede, sem usar recursos de memoria ou processamento.

5. Conclusoes e Trabalhos Futuros

Neste trabalho foi feita uma analise dos aspectos sociais de tres cenarios de mobilidadereais: estudantes nos campus universitarios de Dartmouth e USC e taxis na cidade de SaoFrancisco, EUA. Esses cenarios foram modelados como grafos temporais em que os in-divıduos sao os nos e os encontros entre indivıduos sao as arestas. A partir da comparacaodesses grafos com grafos aleatorios que possuem as mesmas caracterısticas foi possıvelidentificar quais encontros sao provenientes de relacoes sociais e quais sao provenientesde encontros aleatorios. Enquanto os cenarios dos campi universitarios possuem fortescaracterısticas de uma rede social, o cenario dos taxis e muito semelhante a uma redealeatoria.

Page 13: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

Como trabalho futuro, planeja-se estudar novos cenarios de mobilidade real, alemdos cenarios gerados por modelos que existem na literatura. Alem disso, acredita-se que ouso de outras metricas de redes complexas, como, por exemplo, metricas de centralidade,pode melhorar significativamente o desempenho do classificador de relacionamentos. Porfim, pretende-se avaliar mais detalhadamente o algoritmo degeracao de grafos aleatoriosproposto neste trabalho a fim de que se possa entender os seus limites assintoticos de erro.

ReferencesAlbert, R., Jeong, H., and Barabasi, A.-L. (1999). Diameter of the World Wide Web.Nature, 401:130–131.

Backstrom, L., Huttenlocher, D., Kleinberg, J., and Lan, X.(2006a). Group formation in large socialnetworks: membership, growth, and evolution. InKDD ’06: Proceedings of the 12th ACM SIGKDD,pages 44–54, New York, NY, USA. ACM.

Backstrom, L., Huttenlocher, D., Kleinberg, J., and Lan, X.(2006b). Group formation in large socialnetworks: membership, growth, and evolution. InKDD ’06: Proceedings of the 12th ACM SIGKDDinternational conference on Knowledge discovery and data mining, pages 44–54, New York, NY, USA.ACM.

Barbera, M., Stefa, J., Viana, A., de Amorim, M., and Boc, M. (2011). VIP delegation: Enabling VIPs tooffload data in wireless social mobile networks. InProc. of IEEE DCOSS, pages 1 –8.

Conti, M., Di Pietro, R., Gabrielli, A., Mancini, L. V., and Mei, A. (2010). The Smallville Effect: SocialTies Make Mobile Networks More Secure Against the Node Capture Attack. InACM MobiWac.

Crandall, D., Cosley, D., Huttenlocher, D., Kleinberg, J.,and Suri, S. (2008). Feedback effects betweensimilarity and social influence in online communities. InProceedings of 14th ACM SIGKDD, pages160–168, New York, NY, USA. ACM.

Daly, E. M. and Haahr, M. (2007). Social network analysis forrouting in disconnected delay-tolerantmanets. InProceedings of the 8th ACM international symposium on Mobile ad hoc networking andcomputing, MobiHoc ’07, pages 32–40, New York, NY, USA. ACM.

E. M. Daly and M. Haahr (2009). Social Network Analysis for Information Flow in Disconnected Delay-Tolerant MANETs.IEEE Transactions on Mobile Computing, 8(5):606–621.

Erdos, P. and Renyi, A. (1960). On the evolution of random graphs.Publ. Math. Inst. Hung. Acad. Sci.,7:17.

Gonzalez, M. C., Hidalgo, C. A., and Barabasi, A.-L. (2008).Understanding individual human mobilitypatterns.Nature, 453:779–782.

Henderson, T., Kotz, D., and Abyzov, I. (2004). The changingusage of a mature campus-wide wireless net-work. InProceedings of the 10th annual international conference onMobile computing and networking,MobiCom ’04, pages 187–201, New York, NY, USA. ACM.

Hidalgo, C. A. and Rodriguez-Sickert, C. (2008). The dynamics of a mobile phone network.Physica A:Statistical Mechanics and its Applications, 387(12):3017 – 3024.

Hossmann, T., Legendre, F., and Spyropoulos, T. (2009). From contacts to graphs: pitfalls in using complexnetwork analysis for dtn routing. InProceedings of the 28th IEEE international conference on ComputerCommunications Workshops, INFOCOM’09, pages 260–265, Piscataway, NJ, USA. IEEE Press.

Hui, P., Crowcroft, J., and Yoneki, E. (2008). Bubble rap: social-based forwarding in delay tolerant net-works. InACM MobiHoc.

jen Hsu, W. and Helmy, A. (2005). Impact: Investigation of mobile-user patterns across university campusesusing wlan trace analysis.CoRR, abs/cs/0508009.

Page 14: Usando Redes Aleatorias na An´ alise de Mobilidade´Katia.Jaffres/Fichiers/2012SBRC.pdf · tendido para grafos temporais e, ... que sao grupos de indiv˜ ´ıduos fortemente conecta-

Johnson, N. and Kotz, S. (1977).Urn models and their application: an approach to modern discreteprobability theory. WILEY SERIES in PROBABILITY and STATISTICS: APPLIED PROBABILITYand STATIST ICS SECTION Series. Wiley.

Katsaros, D., Dimokas, N., and Tassiulas, L. (2010). Socialnetwork analysis concepts in the design ofwireless ad hoc network protocols.Netwrk. Mag. of Global Internetwkg., 24:23–29.

Kochem Vendramin, A. C., Munaretto, A., Regattieri Delgado, M., and Carneiro Viana, A. (2011). GrAnt:Inferring Best Forwarders from Complex Networks’ Dynamicsthrough a Greedy Ant Colony Optimiza-tion. Rapport de recherche RR-7694, INRIA.

Kumar, R., Novak, J., and Tomkins, A. (2006). Structure and evolution of online social networks. InKDD’06: Proceedings of the 12th ACM SIGKDD, pages 611–617, New York, NY, USA. ACM.

Leskovec, J., Backstrom, L., Kumar, R., and Tomkins, A. (2008). Microscopic evolution of social networks.In KDD ’08: Proceeding of the 14th ACM SIGKDD, pages 462–470, New York, NY, USA. ACM.

Mary Schurgot and Cristina Comaniciu and Katia Jaffres-Runser (2012). Beyond Traditional DTN Routing:Social Networks for Opportunistic Communication.accepted for publication in IEEE CommunicationsMagazine.

Miklas, A. G., Gollu, K. K., Chan, K. K. W., Saroiu, S., Gummadi, K. P., and De Lara, E. (2007). Exploitingsocial interactions in mobile systems. InProceedings of the UbiComp ’07, pages 409–428, Berlin,Heidelberg. Springer-Verlag.

Mislove, A., Marcon, M., Gummadi, K. P., Druschel, P., and Bhattacharjee, B. (2007). Measurement andanalysis of online social networks. InIMC ’07: Proceedings of the 7th ACM SIGCOMM conference onInternet measurement, pages 29–42, New York, NY, USA. ACM.

Mtibaa, A., May, M., Diot, C., and Ammar, M. (2010). Peoplerank: Social opportunistic forwarding. InIEEE Infocom.

Newman, M. (2003). The structure and function of complex networks.

Piorkowski, M., Djukic, N. S., and Grossglauser, M. (2009).A Parsimonious Model of Mobile PartitionedNetworks with Clustering. InThe First International Conference on COMmunication Systems and NET-workS (COMSNETS), Bangalore, India.

Rojas, A., Branch, P., and Armitage, G. (2005). Experimental validation of the random waypoint mobilitymodel through a real world mobility trace for large geographical areas. InProceedings of the 8th ACMinternational symposium on Modeling, analysis and simulation of wireless and mobile systems, MSWiM’05, pages 174–177, New York, NY, USA. ACM.

Thakur, G. S., Helmy, A., and Hsu, W.-J. (2010). Similarity analysis and modeling in mobile societies: themissing link. InProc. ACM CHANTS, pages 13–20.

Watts, D. J. and Strogatz, S. H. (1998). Collective dynamicsof ”small-world” networks.Nature, 393:440–442.

Zyba, G., Voelker, G. M., Ioannidis, S., and Diot, C. (2011).Dissemination in opportunistic mobile ad-hocnetworks: The power of the crowd. InProceedings of IEEE INFOCOM 2011, pages 1179–1187. IEEE.


MANUAL DE INSTALACION Y MANTENIMIENTO …aircalo.fr/fichiers/aircalo_water_heater_ventiz_05_13_mes_es.pdf · sados debe tener una pendiente suficiente para permitir un desagüe por

MANUAL DE INSTALACION Y MANTENIMIENTO …aircalo.fr/fichiers/aircalo_water_heater_ventiz_05_13_mes_es.pdf · sados debe tener una pendiente suficiente para permitir un desagüe por

SOLUCIONARI - UNITAT 4 - disciplines.ac-montpellier.frdisciplines.ac-montpellier.fr/catalan/sites/catalan/files/fichiers/... · 6- La meva àvia prepara - un plat de faves amb vedella.

SOLUCIONARI - UNITAT 4 - disciplines.ac-montpellier.frdisciplines.ac-montpellier.fr/catalan/sites/catalan/files/fichiers/... · 6- La meva àvia prepara - un plat de faves amb vedella.

MANUAL DE INSTALACION Y MANTENIMIENTO FAN …aircalo.fr/fichiers/aircalo_cassette_bora_10_14_mes_es.pdf · 5 Recepción - Almacenamiento Verifique el buen estado de las mercancías

MANUAL DE INSTALACION Y MANTENIMIENTO FAN …aircalo.fr/fichiers/aircalo_cassette_bora_10_14_mes_es.pdf · 5 Recepción - Almacenamiento Verifique el buen estado de las mercancías

lobios - updlimiaverin.files.wordpress.com  · Web viewTanto na Construción como en Servizos, os contratos indefinidos seguen ós temporais, ... motocicletas e ciclomotores e artigos

lobios - updlimiaverin.files.wordpress.com  · Web viewTanto na Construción como en Servizos, os contratos indefinidos seguen ós temporais, ... motocicletas e ciclomotores e artigos

Comissão Organizadora - IEHCAiehca.eu/sites/default/files/fichiers/programa_conference_diaita.pdf · À mesa nas ilhas dos Açores: doces comeres de festa e promessa Lílian Ferreira,

Comissão Organizadora - IEHCAiehca.eu/sites/default/files/fichiers/programa_conference_diaita.pdf · À mesa nas ilhas dos Açores: doces comeres de festa e promessa Lílian Ferreira,

DEÍCTICOS E PERSUASÃO · 2019. 5. 22. · DECTICOS E PERSUASÃO NO DISCURSO PUBLICITÁRIO 293 já clássica dos deícticos: pessoais, espaciais e temporais; avançaremos com observações

DEÍCTICOS E PERSUASÃO · 2019. 5. 22. · DECTICOS E PERSUASÃO NO DISCURSO PUBLICITÁRIO 293 já clássica dos deícticos: pessoais, espaciais e temporais; avançaremos com observações

Nivel - disciplines.ac-montpellier.frdisciplines.ac-montpellier.fr/.../espagnol/files/fichiers/travail_qr_code_et_lrtice.pdf · ciones y/o estados emocionales constituyendo, además,

Nivel - disciplines.ac-montpellier.frdisciplines.ac-montpellier.fr/.../espagnol/files/fichiers/travail_qr_code_et_lrtice.pdf · ciones y/o estados emocionales constituyendo, además,

TIPOS DE MEZCLADORAS MEZCLADORAS › fichiers › trm_produit › ... · tado de excelente calidad, con perseverancia, dedicación al de servicio de la productividad. Creada en 1952

TIPOS DE MEZCLADORAS MEZCLADORAS › fichiers › trm_produit › ... · tado de excelente calidad, con perseverancia, dedicación al de servicio de la productividad. Creada en 1952

¡Desde hace 60 años, René TOY, MANUTENCION GAMA …groupetoy.com/toy/fichiers/trm_produit/RTOY_MANUTENTION2014_Es.pdf · Instalaciones de transportes / manutención Sus unidades

¡Desde hace 60 años, René TOY, MANUTENCION GAMA …groupetoy.com/toy/fichiers/trm_produit/RTOY_MANUTENTION2014_Es.pdf · Instalaciones de transportes / manutención Sus unidades

Logística inversa no mercado de telemóveis em Portugal · 2019-06-09 · logística inversa é relativamente diferente nas três empresas, e que é fortemente influenciado pelas

Logística inversa no mercado de telemóveis em Portugal · 2019-06-09 · logística inversa é relativamente diferente nas três empresas, e que é fortemente influenciado pelas

PL ANA - aquitaine.culture.gouv.fraquitaine.culture.gouv.fr/fichiers... · SARRERA 1) Planaren testuingurua Gaur egun euskararen egoera larria da. 1997 urteko Euskal Herriko Antolaketa

PL ANA - aquitaine.culture.gouv.fraquitaine.culture.gouv.fr/fichiers... · SARRERA 1) Planaren testuingurua Gaur egun euskararen egoera larria da. 1997 urteko Euskal Herriko Antolaketa

SPARE PARTS CATALOGUE ... - extranet.furnotel.comextranet.furnotel.com/global/upload/documents/fichiers/native/6777.pdf · Niagara 281 10-02-2009. NIAGARA 281 Tav.1: ... Tav.7: Pompa

SPARE PARTS CATALOGUE ... - extranet.furnotel.comextranet.furnotel.com/global/upload/documents/fichiers/native/6777.pdf · Niagara 281 10-02-2009. NIAGARA 281 Tav.1: ... Tav.7: Pompa

GAMA DE ALMACENAMIENTO - groupetoy.comgroupetoy.com/toy/fichiers/trm_produit/RTOY_STOCKAGE2014_Es-4.pdf · Bajo silo, Big-Bag, vacía saco 250 Litros Almacenamiento / carga maíz

GAMA DE ALMACENAMIENTO - groupetoy.comgroupetoy.com/toy/fichiers/trm_produit/RTOY_STOCKAGE2014_Es-4.pdf · Bajo silo, Big-Bag, vacía saco 250 Litros Almacenamiento / carga maíz

O ESTADO DE EXCEÇÃO NA CONSTITUIÇÃO DA REPÚBLICA DE …€¦ · - as fases do procedimento para a sua declaração; - os efeitos materiais, organizatórios, espaciais e temporais

O ESTADO DE EXCEÇÃO NA CONSTITUIÇÃO DA REPÚBLICA DE …€¦ · - as fases do procedimento para a sua declaração; - os efeitos materiais, organizatórios, espaciais e temporais

AVIS COMPÉTITION FINALE RÉGIONALE STAR/MICHEL-PROULX …gsh-blanc.com/data/arpae/fichiers/finales_regionales_2016_resultats... · Name Element Score Prog Comp Score Bonus Deductions

AVIS COMPÉTITION FINALE RÉGIONALE STAR/MICHEL-PROULX …gsh-blanc.com/data/arpae/fichiers/finales_regionales_2016_resultats... · Name Element Score Prog Comp Score Bonus Deductions

ROTEIRO LITERARIO DE “A ESMORGA”...ROTEIRO LITERARIO DE “A ESMORGA” ESPACIOS URBANOS DA NOVELA DE EDUARDO BLANCO AMOR Ourense é unha cidade fortemente literaturizada. Moitos

ROTEIRO LITERARIO DE “A ESMORGA”...ROTEIRO LITERARIO DE “A ESMORGA” ESPACIOS URBANOS DA NOVELA DE EDUARDO BLANCO AMOR Ourense é unha cidade fortemente literaturizada. Moitos

2. ENSAIOS EN PROCEDENCIAS DE P. pinaster MELLORA … · países como Xapón están a apostar fortemente pola mellora xenética, encontrando árbores tolerantes á enfermidade nas

2. ENSAIOS EN PROCEDENCIAS DE P. pinaster MELLORA … · países como Xapón están a apostar fortemente pola mellora xenética, encontrando árbores tolerantes á enfermidade nas

Miguel de la Rosa Telefonicacle.ens-lyon.fr/espagnol/fichiers/miguel_de_la_rosa_telefonica_1284742161973.pdfTelefónica Internacional S.A.U. 2 Resumen Telefónica es, sin duda, una

Miguel de la Rosa Telefonicacle.ens-lyon.fr/espagnol/fichiers/miguel_de_la_rosa_telefonica_1284742161973.pdfTelefónica Internacional S.A.U. 2 Resumen Telefónica es, sin duda, una

EX-AEQUOCIENCIA · súa obra pictórica primeira está fortemente influenciada polas raíces da súa terra, sendo unha das súas temáticas recorrentes as cunchas mariñas, interesándose

EX-AEQUOCIENCIA · súa obra pictórica primeira está fortemente influenciada polas raíces da súa terra, sendo unha das súas temáticas recorrentes as cunchas mariñas, interesándose

MINISTERIO DE POLÍTICA TERRITORIAL E ADMINISTRACIÓN … · restauración de coleccións, a programación de exposicións temporais, a reordenación das coleccións, a posta en marcha

MINISTERIO DE POLÍTICA TERRITORIAL E ADMINISTRACIÓN … · restauración de coleccións, a programación de exposicións temporais, a reordenación das coleccións, a posta en marcha