info.info-mc info.info-mo info.info-ni
Pedro O S Vaz De Melo 
  
Alinec Viana 
email: aline.viana@inria.fr
  
Marco Fiore 
email: marco.fiore@insa-lyon.fr
  
Katiajaffrès -Runser 
  
Frédéric Le Mouël 
email: frederic.le-mouel@insa-lyon.fr
  
Antonio A F Loureiro 
email: loureiro@dcc.ufmg.br
  
  
  
  
Usando Redes Aleatórias na Análise de Mobilidade

The constant advancement of information systems has allowed more data to be generated and stored from the most diverse situations. It is fascinating 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 networks. The analysis assumes that these systems are composed ofe n t i t i e sa b l e 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.

cisco (EUA), ou grandes campus universitários, tais como USC, MIT, Dartmouth e UF. Em [START_REF] Thakur | Similarity analysis and modeling in mobile societies: the missing link[END_REF], os autores observaram distribuic ¸ões de similaridade das populac ¸ões de usuários móveis dessas bases de dados e verificaram que os atuais modelos de mobilidade falham em capturar o comportamento dos indivíduos de forma precisa. Numerosos protocolos baseados em aspectos sociais da mobilidade também têm lidado com o problema de previsão de futuros contatos em redes intermitentes. Essas obras são baseadas no fato de que o comportamento humano tende a ter ump a d r ão espac ¸o-temporal, repetindo locais e horários do dia e mostrando algum grau de regularidade [START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF]]. Assim, pode-se avaliar, pore x e m p l o ,op o t e n c i a ld o s nós da rede para atuarem como disseminadores ou roteadores de mensagens a partir de métricas de redes complexas, tal como a centralidade [E. M. [START_REF] Daly | Social Network Analysis for Information Flow in Disconnected Delay-Tolerant MANETs[END_REF][START_REF] Barbera | VIP delegation: Enabling VIPs to offload data in wireless social mobile networks[END_REF][START_REF] Kochem Vendramin | GrAnt: Inferring Best Forwarders from Complex Networks' Dynamics through a Greedy Ant Colony Optimization[END_REF]].

Ofocodestetrabalhoéestudarcenários reais de mobilidade a partir de uma modelagem usando redes complexas temporais. A análise parte do pressuposto que esses sistemas são compostos de entidades capazes de interagir entre si de umamaneiraracional, refletindo seus interesses e dinâmica de atividade. Chamamos esses sistemas de Redes Complexas baseadas em Decisão (RCBDs), essas entidades de nós (ou agentes) ea si n t e r a c ¸ões entre os nós, de arestas. A principal característica de uma RCBD é que ela evolui de acordo com as decisões tomadas pelos agentes desses sistemas, as quais são guiadas principalmente por suas motivac ¸ões pessoais [Backstrom et al. 2006a[START_REF] Kumar | Structure and evolution of online social networks[END_REF][START_REF] Leskovec | Microscopic evolution of social networks[END_REF][START_REF] Mislove | Measurement and analysis of online social networks[END_REF]]. Além disso, RCBDs são caracterizadas por terem um grande número de vértices e arestas que apresentam um padrão como, por exemplo, comunidades ou vértices altamente conectados, chamados hubs [START_REF] Albert | Diameter of the World Wide Web[END_REF]. Enquanto em uma rede simples, com no máximo centenas de nós, o olho humano éu mi n s t r u m e n t od ep o d e rc o n s i d e rável, em uma rede complexa, esta abordagem éinútil. Assim, para estudar, analisar e caracterizar as redes complexas, métodos estatísticos e algoritmos eficientes são necessários.

Este trabalho propõe uma técnica para analisar cenários de mobilidade a partir de grafos aleatórios. Resumidamente essa técnica verifica como o sistema real evoluiria caso as decisões dos seus agentes fossem aleatórias. Mais especificamente, usa-se um algoritmo que, a partir de uma rede real, constrói uma versão aleatória contendo o mesmo número de nós, arestas e distribuic ¸ão empírica do grau dos nós. Esse algoritmo ée stendido para grafos temporais e, a partir dele, pode-se verificar, por exemplo, quais arestas são aleatórias e quais são provenientes de relac ¸ões sociais, tais como relac ¸ões de amizade ou profissionais. Essa classificac ¸ão pode ser usada em diferentes aplicac ¸ões. Por exemplo, o administrador de uma empresa de dispositivos móveis pode usar este método para detectar as relac ¸ões sociais de seus clientes e, portanto, usar esse conhecimento para disseminar dados entre os clientes sem a utilizac ¸ão da infraestrutura da rede [START_REF] Daly | Social network analysis for routing in disconnected delay-tolerant manets[END_REF][START_REF] Hossmann | Fromcontactstographs:pitfallsinusingcomplex network analysis for dtn routing[END_REF][START_REF] Katsaros | Social network analysis concepts in the design of wireless ad hoc network protocols[END_REF]. Ao saber como classificar um encontro como aleatório ou social, reduz-se o grau máximo de um nóaum número viável e escalável, reduzindo o espac ¸o de armazenamento.

Este trabalho estáorganizadodaseguintemaneira.Assec ¸ão 2 descreve os trabalhos relacionados. A sec ¸ão 3 apresenta como éfeitaamodelagemdecenários de mobilidade em redes complexas temporais e também como se constrói a rede aleatória correspondente. A sec ¸ão 4 discute três possíveis aplicac ¸ões para a modelagem proposta neste trabalho: classificac ¸ão de relacionamentos, predic ¸ão de futuros encontros e disseminac ¸ão de dados. Finalmente, a sec ¸ão 5 apresentada as conclusões e trabalhos futuros.

Trabalhos Relacionados

Aanálise dos aspectos sociais de sistemas complexos éfundamentalparaacompreensão das motivac ¸ões por trás das ac ¸ões de suas entidades. Ao revelar as razões por trás das decisões, ép o s s ível separar os eventos aleatórios daqueles movidos por relac ¸ões sociais. Em [START_REF] Crandall | Feedback effects between similarity and social influence in online communities[END_REF], por exemplo, foi mostrado que a ocorrência de arestas na rede estár e l a c i o n a d ac o ma ss e m e l h a n c ¸a se n t r eo snós. Em outro exemplo interessante, [Backstrom et al. 2006b] mostra que a probabilidade de um indivíduo a entrar em uma comunidade éi n fl u e n c i a d an ão sóp e l onúmero de amigos que ele tem na comunidade, mas principalmente pela forma como os amigos estão conectados entre si.

Os lac ¸os sociais entre os usuários têm sido amplamente explorado em redes móveis oportunistas de modo a favorecer os servic ¸os de rede.

Os problemas considerados vão desde o encaminhamento de mensagens multi-hop [START_REF] Hui | Bubble rap: social-based forwarding in delay tolerant networks[END_REF][START_REF] Mtibaa | Peoplerank: Social opportunistic forwarding[END_REF][START_REF] Schurgot | Beyond Traditional DTN Routing: Social Networks for Opportunistic Communication[END_REF] e multicasting, a seguranc ¸a da rede [START_REF] Conti | The Smallville Effect: Social Ties Make Mobile Networks More Secure Against the Node Capture Attack[END_REF]. Em [START_REF] Hui | Bubble rap: social-based forwarding in delay tolerant networks[END_REF][START_REF] Mtibaa | Peoplerank: Social opportunistic forwarding[END_REF], por exemplo, os autores utilizam métricas sociais derivadas de comunicac ¸ões entre os usuários para melhorar a eficiência das decisões de encaminhamento oportunistas el i m i t a n d o ,s i m u l t a n e a m e n t e ,as o b r e c a r g ad ac o m u n i c a c ¸ao. Todas as obras acima tentar explorar a regularidade e os repetidos padrões espac ¸o-temporais esperado no comportamento humano e tendem a ignorar as ligac ¸ões aleatórias ou não-sociais entre os usuários móveis. Em vez disso, focamos na análise simultânea das relac ¸ões aleatórias e social entre os indivíduos.

Atéoa l c a n c ed on o s s oc o n h e c i m e n t o ,[ M i k l a se ta l .2 0 0 7 ]e[ Z y b aetal.2011] são os trabalhos mais estreitamente relacionados com o apresentado aqui. [START_REF] Zyba | Dissemination in opportunistic mobile ad-hoc networks: The power of the crowd[END_REF]] distingue usuários sociais e itinerantes de acordo com seu comportamento de mobilidade: regularidade ou durac ¸ão das visitas em uma determinada área. [START_REF] Miklas | Exploiting social interactions in mobile systems[END_REF]] classifica as arestas entre amigos ed e s c o n h e c i d o s ,s e n d oq u e encontros frequentes entre pares de nós caracterizam interac ¸ões de amizade. Os autores definiram empiricamente que indivíduos que se encontraram 10 dias ou mais dos 101 dias são amigos, outros são estranhos. Neste trabalho usamos redes aleatórias para definir olimitequesepararelac ¸ões sociais de aleatórias.

Modelagem

Fundamentos

Dentre as principais características verificadas em redes sociais reais, destaca-se ap r e s e n c ad ec o m u n i d a d e s , q u es ão grupos de indivíduos fortemente conectados entre si porque compartilham os mesmos interesses ou dinâmicas de atividades [Backstrom et al. 2006a[START_REF] Kumar | Structure and evolution of online social networks[END_REF]. A formac ¸ão dessas comunidades só é possível porque a criac ¸ão das arestas reflete as decisões sociais dos indivíduos, que geralmente são regulares e tendem a se repetir. Por outro lado, em uma rede aleatória as arestas são criadas independentemente dos atributos de cada nó, ou seja, um nó i tem a mesma probabilidade p de se conectar a qualquer outro nó j da rede.

Assim, uma métrica interessante para diferenciar uma rede aleatória de uma rede social éocoeficientedeaglomerac ¸ão da rede. O coeficiente de aglomerac ¸ão cc i de um nó i caracteriza a densidade de conexões próximas a i.M a i s e s p e c i fi c a m e n t e , e l e m e d e ap r o b a b i l i d a d ed ed o i sv i z i n h o sd on ó i serem conectados entre si [START_REF] Newman | The structure and function of complex networks[END_REF]]. Ele éc a l c u l a d od i v i d i n d oonúmero total de arestas que existe entre os vizinhos do nó i pelo número de arestas possível entre eles. O coeficiente de agrupamento da rede éam édia cc i , ∀i ∈ V .P o r c a u s a d a e x i s t ência de comunidades, as redes sociais têm um coeficiente de aglomerac ¸ão alto, enquanto uma rede aleatória tem um coeficiente de aglomerac ¸ão baixo, uma vez que as arestas são uniformemente distribuídas na rede [START_REF] Watts | Collective dynamics of "small-world" networks[END_REF]. No restante deste trabalho, esse conceito éu s a d op a r a diferenciar redes aleatórias de redes sociais.

Redes Complexas baseadas em Decisão

Ap r i n c i p a lc a r a c t e r ística das RCBDs éq u ea si n t e r a c ¸ões entre as suas entidades são, geralmente, consequência de decisões semi-racionais. Escreve-se "normalmente" e decisões "semi-racionais" porque qualquer sistema estás u j e i t oae v e n t o sa l e a tórios e escolhas irracionais. No entanto, uma vez que a maioria das interac ¸ões ainda decorrem de decisões conscientes feitas por suas entidades, a evoluc ¸ão de RCBDs és i g n i fi c a t i v amente diferente da evoluc ¸ão de redes aleatórias como, por exemplo, redes de Erdös and Rényi [START_REF] Erdös | On the evolution of random graphs[END_REF]. Assim, enquanto em uma RCBD as arestas são geradas ap a r t i rd ed e c i sões semi-racionais, que tendem a ser regulares e a se repetir,e mu m a rede aleatória as arestas são geradas independentemente dos atributos dos nós, ou seja, a probabilidade de dois nós se conectarem éconstante.

Considere, por exemplo, uma rede de pessoas e suas rotinas de mobilidade. Uma interac ¸ão entre duas pessoas ocorre se elas se encontram. Se Silva e Moreira trabalham no mesmo escritório e suas horas de trabalho são de 8:00 às 18:00, pode-se prever facilmente que uma interac ¸ão entre Silva e Moreira iráo c o r r e re mt o r n od e8 : 0 0d u r a n t eo s dias da semana. Entretanto, se o proprietário da empresa decide alterar o horário de trabalho para de 12:00 às 20:00, então équasecertoqueessainterac ¸ão também se moverá diariamente para 12:00. Tudo isso ébaseadonofatodequeacreditamosfortementeque tanto Silva quanto Moreira decidirão ir ao trabalho todos os dias pontualmente, jáq u e este é, provavelmente, a decisão racional para se tomar.

Por outro lado, a maioria dos cenários estásujeitaaeventosaleatórios que podem desviar o comportamento esperado dos agentes. No exemplo anterior, Silva pode esquecer da mudanc ¸a de horário da empresa e chegar ao trabalho no mesmo horário como antes, ou seja, às 8:00. Além disso, ele poderia ficar preso no trânsito e se atrasar. O fato éque, apesar de decisões racionais serem regulares, as decisões aleatórias podem muitas vezes ocorrer também.

Formalmente, um agente pode executar uma decisão social D s ou uma decisão aleatória D a .E l et e mu m ap r o b a b i l i d a d ep s da execuc ¸ão de uma decisão social D s e uma probabilidade p r =1p s da execuc ¸ão de uma decisão aleatória D a .I n t u i t i v a m e n t e , quando p s p r ,aredenormalmentee v oluiparaumaredesocialbemestruturada, com ap r e s e n c ¸ad et o d a sa sc a r a c t e r ísticas comuns de uma rede social vistas na sec ¸ão 2, tais como a presenc ¸a de comunidades e hubs.P o ro u t r ol a d o ,q u a n d op r p s ,ar e d en o rmalmente desenvolve características de uma rede aleatória, como as redes de Erdös e Rényi [START_REF] Erdös | On the evolution of random graphs[END_REF].

Este trabalho analisa três conjuntos de dados públicos de mobilidade. O conjunto de dados da Universidade de Dartmouth [Henderson et al.2 0 0 4 ] ( r e d e D a r tmouth), que contém registros de mobilidade de mais de mil pessoas dentro do campus de Dartmouth, durante mais de oito semanas. O conjunto de dados do campus da USC [jen Hsu and Helmy 2005] (rede USC), que também contém registros de mobilidade em um cenário de campus universitário, com mais de quatro mil indivíduos durante mais de oito semanas. Finalmente, o conjunto de dados de mobilidade de táxis em São Francisco (EUA) [START_REF] Rojas | Experimentalvalidationoftherandomwaypointmobility model through a real world mobility trace for large geographical areas[END_REF]] (rede Táxi), que contém registros da mobilidade de 551 táxis dentro da cidade, durante quatro semanas. Em todos os casos analisamos as ocorrências de contato entre dois indivíduos, onde para cada evento éregistradooinicio ead u r a c ¸ão do contato, todos na precisão de segundos. Nos registros de Dartmouth e USC, dois indivíduos estão em contato se eles estão usando o mesmo ponto de acesso sem fio(wireless access point)paraseconectaràrededocampus. Nosre gistrosdetáxi, dois indivíduos estão em contato se a distância for inferior a 250 metros, que éoalcance máximo de uma rede padrão IEEE 802.11 [START_REF] Piorkowski | AParsimoniousModelofMobilePartitioned Networks with Clustering[END_REF]]. Mais detalhes dos conjuntos de dados que utilizamos neste trabalho são descritos na tabela 3.2. Opesow t (i, j) de uma aresta (i, j) émodeladocomoapersistência dessa aresta desde o tempo inicial 1 atéot e m p oc o r r e n t et [START_REF] Hidalgo | The dynamics of a mobile phone network[END_REF]. Nos conjuntos de dados de Dartmouth e da USC, um intervalo de tempo éoper íodo de 24 horas. No conjunto de dados dos táxis, um intervalo de tempo édequatrohoras. Por exemplo, no conjunto de dados de Dartmouth, considerando queosnós i e j se reuniram em 15 dias dos últimos 30 dias, então a persistência da aresta w 30days (i, j)=0.5,ouseja, em 50% dos últimos 30 dias, os nós i e j se encontraram. A grande vantagem de modelar op e s od aa r e s t ac o m oap e r s i s t ência em vez de, por exemplo, a durac ¸ão agregada do contato éque,comapersistência, épossível detectar relac ¸ões regulares e de rotina entre dois indivíduos. Op r i m e i r op a s s op a r aa n a l i s a ro sp a d rões de mobilidade do grafo G t (V t ,E t ) é construir a versão aleatória G R t (V t ,E R t ) do mesmo. Essa versão aleatória deve conter as mesmas características topológicas do grafo real, ou seja, o mesmo número de nós, arestas edistribuic ¸ão empírica do grau. Dessa maneira, a única diferenc ¸a entre G t e G R t estánas conexões entre os nós. Enquanto em G t os nós se conectam "semi-racionalmente", em G R t aconexão éfeitadeformapuramentealeatória. Isso permite verificar com exatidão a extensão da aleatoriedade na mobilidade dos indivíduos nos cenários analisados.

Gerac ¸ão do Grafo Aleatório

Para construir G R , épropostoousodeumalgoritmodeurnatão comum na gerac ¸ão de estruturas aleatórias [START_REF] Johnson | Urn models and their application: an approach to modern discrete probability theory[END_REF]. O primeiro passo do algoritmo éc o l o c a r na urna, para cada nó n i , d i "bolas" marcadas com o identificador i do nó, sendo d i o grau do nó n i .D e p o i sd i s s o ,r e t i r a -s ea l e a t o r i a m e n t ed au r n ad u a sb o l a sb i e b j que estão marcadas com os identificadores i e j dos nós n i e n j .S ei = j enão háu m aa r e s t a (i, j) em G R ,então os nós n i e n j são conectados em G R .E s s ep a s s oérepetidoatéque (i) a urna esteja vazia ou que (ii) não seja mais possível conectar os nós que estão na urna. Quando não ém a i sp o s s ível conectar os nós que estão na urna, háu m ad i f e r e n c ¸a ≈ 0.001% entre o número de arestas de G edeG R ,oqueconsideramosinsignificante. Uma análise mais detalhada sobre deixamos como trabalho futuro. Todo o procedimento de gerac ¸ão de grafos aleatórios édescritonoAlgoritmo1. 

21:

←urna.tamanho() /2 × G.numArestas()

22: fim procedimento

Ap a r t i rd e s s ea l g o r i t m op o d e -s eg e r a ru mg r a f oa l e a tório G R ap a r t i rd eq u a lquer grafo G.N oe n t a n t o ,n e s t et r a b a l h os ão analisados grafos temporais do tipo G t que evoluem àmedidaqueencontrosentreindi v íduos ocorrem. Para gerar o grafo temporal aleatório G R t com as devidas persistências aleatórias nas arestas, executa-se o Algoritmo 1 em cada grafo de evento G t ,criandoassimocorrespondente grafo aleatório de evento G R t .A s s i m ,og r a f oG R t nada mais équeaunião dos grafos aleatórios de eventos ,

G R t = {G R 1 ∪G R 2 ∪...∪G R t }.
Opeso,oupersistência, aleatório de uma aresta (i, j) ∈ E R t écalculadodividindoonúmero de vezes que (i, j) apareceu nos grafos aleatórios de eventos G 1 , G 2 ,...,G t por t.Acomparac ¸ão da persistência real dos encontros com a persistência aleatória permite, por exemplo, verificar a probabilidade de um encontro entre dois nós i e j ocorrer x vezes aleatoriamente em um determinado cenário de mobilidade.

Aplicac ¸ões

Classificac ¸ão

Através da comparac ¸ão de G t com G R t épossível quantificar a probabilidade de uma determinada persistência de uma aresta w(i, j) ser consequência da aleatoriedade de eventos ou de uma relac ¸ão social real. Como os conjuntos de dados de Dartmouth e USC têm oito semanas de registros de mobilidade, usaremos as primeiras sete semanas (base de treino) para classificar as arestas e a última semana (base de teste) para verificar a eficiência da classificac ¸ão. Na base de táxis, que contém quatro semanas de dados, émantidaamesma base de testes de uma semana, ficando três semanas para a base de treino. No final da base de treino, há 175722 arestas na rede de Dartmouth, 1287992 arestas na rede USC rede e 142332 arestas da rede Táxi.

Afi g u r a2m o s t r aad i s t r i b u i c ¸ão cumulativa complementar da persistência das arestas tanto para a rede real G t quanto para a sua correspondente aleatória G R t ,emque t varia atéofi md ab a s ed et r e i n o . P o d e -s eo b s e r v a rn afi g u r a2 -aq u e ,p a r aoc o n j u n t o de dados Dartmouth, as probabilidades de ter valores elevados de persistência éordensde magnitude menor para a rede aleatória em comparac ¸ão com a rede real. De fato, enquanto para a rede de Dartmouth a persistência das arestas éq u a s eu n i f o r m e m e n t ed i s t r i b u ída, para a sua rede aleatória correspondente não existem arestas com persistência superior a 0, 4.P o ro u t r ol a d o ,o b s e r v a -s en afi g u r a2 -bq u e ,p a r aoc o n j u n t ode dados USC háuma diferenc ¸a significativa apenas para altos valores. Isso indica que no cenário USC a mobilidade ésuperioràdocenário Dartmouth, favorecendo constantes encontros aleatórios. Finalmente, para o conjunto de dados Táxi, as distribuic ¸ões de persistência das arestas são praticamente as mesmas. Nesse cenário, uma vez que a mobilidade ésignificati v amente alta, mesmo aleatoriamente pode-se ter uma persistência de 100%.

Como mencionado na Sec ¸ão 3.1, o coeficiente de agrupamento de uma rede é uma métrica interessante para verificar o quão social ou aleatória éar e d e . P o r t a n t o , afi g u r a3m o s t r aoc o m p o r t a m e n t od oc o e fi c i e n t ed ea g r u p a m e n t op a r aa st r ês redes analisadas G t es e u sc o r r e s p o n d e n t e sa l e a tórios G R t ao longo do tempo. A figura 3-a indica que, para o conjunto de dados Dartmouth, nos primeirosd i a soc o e fi c i e n t ed e aglomerac ¸ão de G e G R éd i f e r e n t ee mo r d e n sd em a g n i t u d e . N oe n t a n t o ,a ol o n g o do tempo os seus valores se tornam mais próximos, jáq u em a i se n c o n t r o sa l e a t órios ocorrem. Por outro lado, como vemos na figura 3-b, os coeficientes de aglomerac ¸ão de G e G R para o conjunto de dados USC são quase constantes ao longo do tempo. No entanto, a diferenc ¸a entre eles não étão significativa quanto na rede Dartmouth, possuindo amesmaordemdemagnitude. Finalmente,oscoeficientesdeagrupamento das redes de táxi são praticamente os mesmos, como observa-se na figura 3-c. Isso, juntamente com or e s u l t a d om o s t r a d on afi g u r a2 -c ,i n d i c aq u eG e G R são muito semelhantes para o conjunto de dados Táxi, ou seja, nesse caso p r p s .I s s of a zs e n t i d oj áqueasdecisões tomadas pelos táxis dependem da decisão do indivíduo que éle v adoporelese,umavez que táxis coletam indivíduos ao acaso na rua, p r p s .P o ri s s o ,ap a r t i rd ea g o r asóserão analisados os conjuntos de dados de Dartmouth e USC. Para as redes não-aleatórias, ou seja, Dartmouth e USC, pode-se usar as informac ¸ões observadas na figura 2 para quantificar a probabilidade p w de existir uma aresta com persistência superior a w eq u es e j ac o n s e q u ência de encontros aleatórios. Com isso, pode-se definir um limite T w para a persistência de uma aresta (i, j) de modo que, se w(i, j) <T w ,então essa aresta éclassificadacomoaleatória,casocontrário, como social.A oo b s e r v a ro sv a l o r e sd e(x, y) da curva aleatória na figura 2, pode-se definir um valor de T w que torna a probabilidade p w de erroneamente classificar uma aresta aleatória como social suficientemente pequena e aceitável para uma determinada aplicac ¸ão. Por exemplo, se definirmos T w =0, 4 para a rede de Dartmouth, então a probabilidade de erroneamente classificar uma aresta aleatória como social é ≈ 0. Éimportanteressaltarque esse método écapazdeestimarataxadeerrosdotipofalsopositivoparaaclassificac ¸ão de arestas como sociais (p w ), mas como a base de dados usada neste trabalho não possui a informac ¸ão sobre quais relacionamentos são sociais, não épossível estimar a taxa de erro do tipo falso negativo.

Uma vez que pode-se classificar arestas como sociais e aleatórias, pode-se verificar como as redes evoluiriam caso fossem constituídas somente por um desses dois tipos de arestas. Assim como foi feito na figura 1, a figura 4 ilustra retratos das redes de Dartmouth e USC após uma semana de interac ¸ões, mas considerando apenas as arestas sociais (primeira coluna) ou apenas as arestas aleatórias (segunda coluna). Para a rede de Dartmouth T w =0, 2 e, para a rede USC, T w =0, 1.1 Pode-se observar que, enquanto as redes geradas usando apenas arestas aleatórias são muito semelhantes a uma rede aleatória gerada, por exemplo, pelo modelo de Erdös e Rényi, as redes geradas usando apenas arestas sociais são mais similares com as redes sociais vistas na literatura, com a presenc ¸a clara de comunidades disjuntas. Note também como elas são visualmente diferentes das redes completas vistas na figura 1. 

Predic ¸ão

Dado que as relac ¸ões sociais são regulares e se repetem com o tempo, éinteressanteverificar se as arestas que classificamos como sociais na base de treino aparecem também na base de teste. As figuras 6-a e 6-c mostram a porcentagem de arestas que foram classificadas como sociais e aleatórias no nosso conjunto de treino para um dado valor de T w que também aparece no nosso conjunto de teste. Pode-se observar que àm e d i d aq u eo parâmetro limite T w aumenta, também aumenta a probabilidade de uma aresta classificada como social aparecer também no conjunto de teste. Isso ée x p l i c a d op e l of a t od e que àmedidaqueT w aumenta, a persistência mínima de arestas sociais também aumenta, tornando-as mais propensas a aparecer no futuro. No entanto,ataxadeaparecimentode arestas sociais diminui para a rede USC quando T w > 0, 65,p o i sháp o u c a sa r e s t a sn a rede com persistência superior a este valor (≈ 0.1%,v e rfi g u r a2 ) ,oq u et o r n aaa nálise tendenciosa para essas arestas. Por outro lado, para a rede deD a r t m o u t h ,q u a n d oT w aumenta, mais arestas sociais são erroneamente classificados como aleatórias, o que aumenta a probabilidade de uma aresta classificada como aleatória aparecer no futuro.

Além disso, na Figura 6-b e 6-d, émostradooatrasomédio que as arestas classificadas como sociais e como aleatórios levam para aparecer no conjunto de teste. Como esperado, as arestas sociais geralmente aparecem antes que as arestas aleatórias. Uma vez que as arestas sociais representam encontros regulares ederotina,espera-sequeesse encontro ocorra muitas vezes durante a semana, enquanto encontros aleatórios devem ser distribuídos uniformemente ao longo do tempo. Mais uma vez, àmedidaqueoparâmetro limite T w aumenta, mais arestas sociais são erroneamente classificados como aleatórias, fazendo com que o atraso médio das arestas aleatórias diminua na rede de Dartmouth. 

Disseminac ¸ão de Dados

Dadas todas as evidências de que nossa classificac ¸ão foi eficaz, ép o s s ível monitorar as redes a partir da sua rede social, que desconsidera as conexões aleatórias. O administrador de uma operadora de telefonia móvel, por exemplo, pode usar esse método para detectar as relac ¸ões sociais de seus clientes e, portanto, usar esse conhecimento para disseminar uma informac ¸ão prestada na rede sem a utilizac ¸ão da infraestrutura da rede, como proposto em [START_REF] Daly | Social network analysis for routing in disconnected delay-tolerant manets[END_REF][START_REF] Hossmann | Fromcontactstographs:pitfallsinusingcomplex network analysis for dtn routing[END_REF][START_REF] Katsaros | Social network analysis concepts in the design of wireless ad hoc network protocols[END_REF]].

Nessa direc ¸ão, observa-se, então, como a informac ¸ão se dissemina na rede quando (i) todas as arestas estão disponíveis, (ii) quando apenas arestas sociais estão disponíveis, e(iii)quandoapenasarestasaleatórias estão disponíveis na rede. Mais uma vez, para os pontos (ii) e (iii), para a rede de Dartmouth, T w =0 , 2, e para a rede USC, T w =0 , 1.O número de arestas classificadas como sociais e como aleatórias por conjunto de dados é mostrada na Tabela 4.3.

Uma inundac ¸ão simples do tipo unicast ér e a l i z a d an ar e d eu s a n d of o n t e sd i f erentes e, em seguida, observa-se o tempo de atraso para que os nós sejam atingidos pela disseminac ¸ão de dados. Mais especificamente, éescolhidoumnóaleatório n s para ser o nódeorigem,ouseja,onóquev aicomec ¸aradi vulgarainformac ¸ão. Depois, define-se otempoinicialt 0 como o momento do primeiro contato entre n s eoprimeironóquevai receber a informac ¸ão n i .Oa t r a s ol i do nó i édefinidocomo0,poiséoprimeirocontato. Após a simulac ¸ão, a mediana dos atrasos l écalculadaparatodososatrasosl j para todos os nós n j que foram atingidos pela inundac ¸ão.

Afigura7mostraamédia das medianas dos atrasos l eseusrespectivosintervalos de confianc ¸a de 95%.E mp r i m e i r ol u g a r ,o b s e r v ec o m os ão diferentes os impactos das arestas sociais e aleatórias em ambas as redes. Enquanto na rede Dartmouth as arestas sociais, que representam 48% das arestas, são capazes de propagar informac ¸ão tão bem quanto quando se tem todas as arestas, na rede USC as arestas sociais, que representam 20% das arestas, têm um desempenho significativamente pior. Isso acontece devido às características da distribuic ¸ão da persistência das arestas de cada rede. Enquanto na rede Dartmouth a persistência das arestas éq u a s eu n i f o r m e m e n t ed i s t r i b u ída, na rede USC a distribuic ¸ão équaseexponencial,comasarestasdebaixapersistência (ou arestas aleatórias) dominando a distribuic ¸ão.

Outro fato interessante é que, na rede USC, o desempenho da disseminac ¸ão quando se usa apenas arestas aleatórias ém e l h o rq u eq u a n d os eu s at o d a sa sa r e s t a s . Isso acontece devido àformaquesecalculat 0 ,queécalculadoapenasquandooprimeiro contato ocorre. Assim, quando o primeiro contato éu mc o n t a t os o c i a l ,ad i f u são se espalha apenas na comunidade em que os nós estão inseridos (por exemplo, um laboratório ou uma sala de aula). És a b i d oq u ea sp e s s o a sfi c a mu m aq u a n t i d a d es i g n i fi c a t i v ad e tempo nesses ambientes antes de sair, o que aumenta o atraso. Por outro lado, quando o primeiro contato éu mco n t at oal eatório, isso provavelmente significa que ambos os nós estão em áreas de transic ¸ão ou áreas povoadas, como restaurantes ou arenas esportivas, o que leva a uma rápida disseminac ¸ão entre os indivíduos de diferentes comunidades. Essas observac ¸ões são fundamentais quando se quer divulgar uma informac ¸ão prestada em uma rede sem o uso de um controle central, tais comoai n f r a e s t r u t u r a3 G das operadoras móveis. O projeto de uma soluc ¸ão de disseminac ¸ão deve ser diferente e dependente do cenário analisado. Na rede de Dartmouth, por exemplo, pode-se usar somente arestas sociais para disseminar informac ¸ões, economizando memória (apenas 48% das arestas são sociais quando T w =0, 2)erecursosdeprocessamento(ocálculo de caminhos em grafos menores/esparsos émaisrápido). Por outro lado, uma vez que foi observado que a mobilidade na rede USC éaltaearestasaleatórias divulgam informac ¸ões mais rapidamente que as arestas sociais, então pode-se projetar uma soluc ¸ão de disseminac ¸ão completamente ad hoc,c o mnós propagando informac ¸ões de forma aleatória em toda a rede, sem usar recursos de memória ou processamento.

Conclusões e Trabalhos Futuros

Neste trabalho foi feita uma análise dos aspectos sociais de três cenários de mobilidade reais: estudantes nos campus universitários de Dartmouth e USC e táxis na cidade de São Francisco, EUA. Esses cenários foram modelados como grafos temporais em que os indivíduos são os nós e os encontros entre indivíduos são as arestas. A partir da comparac ¸ão desses grafos com grafos aleatórios que possuem as mesmas características foi possível identificar quais encontros são provenientes de relac ¸ões sociais e quais são provenientes de encontros aleatórios. Enquanto os cenários dos campi universitários possuem fortes características de uma rede social, o cenário dos táxis ém u i t os e m e l h a n t eau m ar e d e aleatória.

Como trabalho futuro, planeja-se estudar novos cenários de mobilidade real, além dos cenários gerados por modelos que existem na literatura. Além disso, acredita-se que o uso de outras métricas de redes complexas, como, por exemplo, métricas de centralidade, pode melhorar significativamente o desempenho do classificador de relacionamentos. Por fim, pretende-se avaliar mais detalhadamente o algoritmo de gerac ¸ão de grafos aleatórios proposto neste trabalho a fim de que se possa entender os seus limites assintóticos de erro.

Figure 1 .

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

Algorithm 1 :

 1 G e r a n d ou mG r a f oA l e a tório G R apartirdeG 1

Figure 2 .

 2 Figure 2. Distribuic ¸ão da persist ência de aresta (peso da aresta) para as tr ês redes analisadas Gs e suas correspondentes aleat órias G R s.

Figure 3 .

 3 Figure 3. Evoluc ¸ão do coeficiente de aglomerac ¸ão das tr ês redes analisadas Gses u a s correspondentes aleat órias G R s.

Figure 4 .

 4 Figure 4. Retratos das redes de Dartmouth e USC depois de 1 semana de interac ¸ões, considerando apenas arestas sociais ou aleat órias.Éi m p o r t a n t et a m bém analisar o comportamento do coeficiente de agrupamento das redes quando elas contêm somente arestas de um determinado tipo, uma vez que

Figure 5 .

 5 Figure 5. Evoluc ¸ão do coeficiente de aglomerac ¸ão das redes de Dartmouth e USC Gs e suas correspondentes redes aleat órias G R sq u a n d osão consideradas apenas arestas sociais ou aleat órias.

Figure 6 .

 6 Figure 6. O impacto do par âmetro limite Tw. (coluna da esquerda) O percentual de arestas que foram classificadas como sociais e como aleat órias que aparecem tamb ém na base de testes (coluna da direita). A mediana do atraso (em horas) para as arestas aparecerem.

Figure 7 .

 7 Figure 7. Comportamento da disseminac ¸ão de dados quando se usa (1) todas as arestas, (2) apenas arestas sociais e (3) apenas arestas aleat órias.

Conjunto de Dados Referência Local Tamanho N úmero de Agentes

  

	Dartmouth	[Henderson et al. 2004]	Campus universitário	700MB	1156
	USC	[jen Hsu and Helmy 2005] Campus universitário	160MB	4558
	Taxi	[Rojas et al. 2005]	Cidade	161MB	551

Table 1 . Conjunto de dados usados neste trabalho. 3.3. Grafo de Mobilidade

 1 

	Neste trabalho, um cenário de mobilidade ém o d e l a d oap a r t i rd eu mg r a f oG t (V t ,E t ),
	em que o conjunto de vértices V t contém os indivíduos que estão nos registros da base
	de dados antes do tempo t eoconjuntodearestasE t representa todos os encontros que
	aconteceram antes do tempo t.A s s i m ,e s s eg r a f oe v o l u ia ol o n g od ot e m p oec o n s i d e r a
	tanto os encontros rotineiros quanto os encontros aleatórios entre dois indivíduos. A
	figura 1 mostra retratos dessas redes em um dado intervalo de tempo. Observe como	é
	difícil comparar as redes usando somente a visualizac ¸ão.	

  Como nenhuma aresta éremovida de G t en o v o se n c o n t r o ss ão sempre agregados, então |E t+1 | > |E t |.A s s i m , para construir um grafo aleatório temporal G R t ,d e c o m p o m o sG t em t grafos de eventos G 1 , G 2 ,...,G t ,emquecadagrafodeeventoG t contém somente os eventos que ocorreram entre os tempos t -1 e t.A s s i m ,G t = {G 1 ∪G 2 ∪ ... ∪G t }.

Table 2 . Par âmetros da disseminac ¸ão de dados.

 2 

Esses valores foram definidos manualmente, visando garantir tanto uma baixa taxa de falso positivos quanto uma quantidade significativa de arestas sociais.