info.info-mc
Felipe Cunha 
  
Extrac ¸ão de Propriedades Sociais em Redes Veiculares

Everyday, vehicles perform routes in a city and along of theirt r ajectories they encounter other vehicles. The frequency of these encounters is influenced by many factors, such as: vehicle speed, destinations, traffic conditions, and the period of the day. However, these factors are justified by the public roads limits and the driver's behavior. The people present daily routines and similar behaviors that have a great impact in the daily trafficevolution. Inthis work, we present a numerical analysis of real and realistic traces data set that describe the mobility of a set of vehicles. Social metrics arecomputed,andthe results obtained are compared to random graphs in the direction to attest that Ve h i c u l a r N e t w o r k p re s e n t s a s o c i a l b e h a v i o r. R e s u l t s s h o w the existence of routines and social properties in Vehicular Networks. Finally,wediscussaboutnew social perspectives in Vehicular Networks.

Introduc ¸ão

As Redes Veiculares (Ve h i c u l a r N e t w o r k s -VA N E T s )sã ou mt i p oe s p e c i a ld er e d e sa dhoc, formadas por veículos que possuem capacidade de processamento e comunicac ¸ão sem fio, transitando por ruas e rodovias. Geralmente, esses veículos podem se comunicar diretamente ou pelo uso de pontos de acesso (RSUs). Através das RSUs pode-se ter acesso eo b t e rd a d o sd eo u t r a sr e d e s ,c o m op o re x e m p l oaI n t e r n e t . D e vido a esta natureza, as redes veiculares podem estabelecer a comunicac ¸ão em diferentes ambientes, como centros urbanos e rodovias [START_REF] Boukerche | Vehicular ad hoc networks: A new challenge for localization-based systems[END_REF].

Essas redes são propostas para ajudar motoristas com o trânsito, para evitar colisões com a emissão de alertas, para prover entretenimento para motoristas e passageiros, et a m bé mp a r ac r i a ru ms i s t e m ad et rá f e g oi n t e l i g e n t e . U m aimportante aplicac ¸ão é a emissão de alertas para os motoristas, com informac ¸ões acerca das condic ¸ões das rodovias e perigos de colisões iminentes. Estudos recentes mostram que 60% dos acidentes de veículos podem ser evitados se os condutores forem avisados segundos antes da colisão [START_REF] Faezipour | Progress and challenges in intelligent vehicle area networks[END_REF]. Assim, uma interac ¸ão entreo sv e í c u l o sp o d ec o n t r i b u i r fortemente para a disseminac ¸ão de uma mensagem de alerta, econsequentementereduzir onúmerodeacidentes [Schochetal.2008].Outroexemplodeaplicac ¸ões é o auxílio aos condutores, com o objetivo de fornecer um melhor caminho. Comisso,éimportanteque essas redes monitorem e prevejam as condic ¸ões de tráfego com sugestões de mudanc ¸as de rota, para evitar engarrafamentos e assim, reduzir o tempo daviagem [T ostesetal.2013].

Nestas redes a comunicac ¸ão é altamente influenciada pela densidade de veículos eo sp a d rõ e sd em o b i l i d a d ed o sm e s m o s . V e í c u l o ss em o v e mep aram de acordo com os limites de velocidade e direc ¸ão impostos pelas vias públicas. Entretanto, o período do dia também pode influenciar na mobilidade. Em horários depico,otráfe gopodeser mais lento, com engarrafamentos; o que forc ¸a o motorista a parar o veículo ou mudar a sua rota. Em contrapartida, os finais de semana, feriados e madrugadas são períodos nos quais o tráfego é ocioso. Esta variac ¸ão de densidade nos horários reforc ¸a a característica dinâmica das redes veiculares, tornando a comunicac ¸ão uma tarefa desafiadora. Amobilidadetambéméinfluenciadapelocomportamentodomotorista e sua rotina. Durante os finais de semana, destinos como: sítio, fazenda, igreja e centros comerciais são escolhidos para lazer e entretenimento, e são frequentemente visitados. Nos dias de semana, um comportamento contrário é observado. Pessoas repetem seus caminhos diariamente, nos mesmos períodos, para os mesmos destinos como: escolas, trabalhos, universidades, restaurantes, etc. Durante suas trajetórias encontram com outros veículos, atravessam as mesmas vias e estão sujeitas as mesmas condic ¸ões de tráfego. Estas características sugerem o estudo da mobilidade veicular sob uma perspectiva social, com ointuitodeentendermelhorsuae v oluc ¸ãoedeaplicarosconceitos sociais obtidos para melhorar as aplicac ¸ões e a conectividade em redes veiculares.

Nesta direc ¸ão, o objetivo deste trabalho é o de investigaras e g u i n t eq u e s t ã o : Quais são as características que uma rede veicular precisa apresentar para comprovar existência de um comportamento social? Assim, este trabalho apresenta uma análise social de duas bases de dados (traces)q u etê mc a r a c t e r í s t i c a sd ed i f e r e n t e sg r u p o sd e veículos. A primeira base é realística e contém registros de dados de veículos durante uma rotina diária. A segunda base é real e contém registrosdamobilidadedetáxisdurante um mês. Esta análise será efetuada a partir do registro de movimento dos veículos e seus encontros, modelados como grafos temporais. Nestes grafos serão computadas métricas que certifiquem a existência de propriedades sociais. Para melhorar a compreensão dos resultados e tornar a análise consistente, algumas métricas serão calculadas também em grafos aleatórios, que serão gerados com a mesma quantidade de vértices e distribuic ¸ão de graus dos grafos temporais. Finalizando, serão apresentados cenários e situac ¸ões nos quais a aplicac ¸ão das métricas sociais em redes veiculares é relevante.

Or e s t a n t ed ot r a b a l h oe s táo r g a n i z a d od as e g u i n t ef o r m a . ASec ¸ão 2 apresenta um breve resumo dos trabalhos relacionados relevantes da literatura. A Sec ¸ão 3 descreve ametodologiautilizadaparaavaliac ¸ãodasbasesdedados.AS e c ¸ã o4a p r e s e n t aa sb a s e s de dados utilizadas e os resultados quantitativos, de acordoc o mc a d amé t r i c aa v a l i a d a . Completando, a Sec ¸ão 5 expõe as conclusões finais e perspectivas futuras.

Trabalhos Relacionados

"As redes de computadores s ão inerentemente redes sociais,l i g a n d oa sp e s s o a s , organizac ¸ões e conhecimento" [START_REF] Wellman | Computer networks as social networks[END_REF]]. Nesta perspectiva, o conceito de redes sociais tem sido explorado em diferentes tipos de redes de computadores, principalmente para melhor entender a evoluc ¸ão da topologia e para analisar os encontros físicos dos nós, com o objetivo de melhorar o desempenho dos protocolos de comunicac ¸ão [START_REF] Scott | Social Network Analysis: A Handbook[END_REF][START_REF] Hossmann | FromContactstoGraphs:PitfallsinUsingComplexNetworkAnalysis for DTN Routing[END_REF] Neste mesmo contexto, em [START_REF] Loulloudes | The dynamics of vehicular networks in urban environments[END_REF], os autoresd i s c u t e mc o m o as métricas sociais podem ser empregadas para melhorar o desempenho dos protocolos de roteamento em redes veiculares. A análise, entretanto, é b a s e a d a e m u m c u r t o p e r í o d o de 2 horas. Acredita-se que um curto período de observac ¸ão não é suficiente para extrair comportamentos sociais de uma mobilidade veicular. Outra análise social é apresentada em [START_REF] Liu | Exploring social properties in vehicular ad hoc networks[END_REF]. Este trabalho discute diversas leis universais das redes sociais e apresenta uma análise numérica de uma real base de dados. Osautoresescolheramduas bases públicas: São Francisco e Shanghai, que descrevem osm o v i m e n t o sd etá x i s . A s métricas sociais foram estimadas e os resultados mostraramaexistênciaderotinassociais em VANETs, comprovando as leis de potência para a distribuic ¸ã o d e g r a u s e o f e n ô m e n o small world.E s t et r a b a l h oc o n s i d e r aa p e n a sam o b i l i d a d ed ab a s ed ed a d o sdetáxisea avalia somente as métricas sociais, sem verificar a existência de rotinas.

Em [START_REF] Uppoor | Insights on metropolitan-scale vehicular mobility from a networking perspective[END_REF]] também é apresentado uma análise de base de dados de veículos. Entretanto os autores se atêm apenas no estudoeclassificac ¸ãodastrajetórias diárias dos condutores. A base de dados avaliada foi da cidade de Cologne e os autores acaracterizaramdeformamacroemicroscópica.Comomacroscópica, com a análise da evoluc ¸ão da densidade de o dinamismo dos fluxos de veículosentreasregiõesnacidade. Em i c r o s có p i c a ,c o maa n á l i s ed ad i s t r i b u i c ¸ã od ev e í c u los por área e a quantidade de encontro entre eles. Contudo, esta análise não considera aspectos sociais e tampouco a interac ¸ão entre os veículos.

Como estudo inicial, em [START_REF] Cunha | How effective is to look at a vehicular network under a social perception?[END_REF], apresentamos umaa v a l i a c ¸ã od e métricas sociais em base de dados de veículos com durac ¸ãode24 horas. Esta avaliac ¸ão apresentou a existência de rotinas sociais e comportamentos similares em redes veiculares. Porém, este estende e aprimora o estudo com a análise de bases de dados com longa durac ¸ão. Os resultados obtidos com esta avaliac ¸ão serão comparados com resultados das métricas aplicadas a grafos aleatórios. Além disso, também será indicado possíveis servic ¸os e protocolos das redes veiculares que poderão fazer uso destas métricas para alcanc ¸ar melhorias de desempenho.

Metodologia

Nesta sec ¸ão serão apresentados os detalhes da metodologia usada em toda a avaliac ¸ão das bases de dados. A execuc ¸ão desta avaliac ¸ão consiste na construc ¸ão de grafos que representam as interac ¸ões entre os veículos e o cálculo das métricas sociais. Assim, nas sec ¸ões a seguir serão descritas as suposic ¸ões feitas naconstruc ¸ãodosgrafostemporaise randômicos e a definic ¸ão das métricas avaliadas.

Grafos Temporais

Omodeloutilizadoparaconstruc ¸ãodosgrafostemporaisconsidera a existência de duas arestas entre os vértices quando dois veículos tiveram um encontro, isto é, um veículo está localizado fisicamente dentro do raio e comunicac ¸ão do outro. Nessa avaliac ¸ão o raio de comunicac ¸ão considerado foi de 100 metros, de acordo comop r o t o c o l o802.11p eo cenário de centros urbanos. Conforme padronizac ¸ão entreasbasesavaliadas,avelocidade média dos veículos foi de 25km/h. Assim, de acordo com esta velocidade e o raio de comunicac ¸ão, os registros de posic ¸ão dos veículos sãoa n a l i s a d o s . S e m p r eq u eh o u v e r dois veículos próximos e a diferenc ¸a do registro de data/hora entre eles for de 15 s., um encontro será registrado no grafo. 

Grafos Aleatórios

Um grafo aleatório é um grafo obtido a partir de um conjunto de vértices V es u ar e spectiva distribuic ¸ão de graus. A adic ¸ão de arestas no grafo G R é f e i t a d e f o r m a a l e a t ó r i a , baseado em modelos de probabilidade. Neste trabalho, o processo de construc ¸ão dos grafos aleatórios G R baseia-se no algoritmo de urna, usado na gerac ¸ão de estruturas aleatórias [START_REF] Johnson | Urn Models and Their Applications: An Approach to Modern Discrete Probability Theory[END_REF]. Nele, o primeiro passo consiste na inserc ¸ão de d i "bolas" em uma urna, marcadas com o identificador i do vértice, de forma que d i corresponde ao grau do vértice i.F e i t oi s s op a r at o d o so sv é r t i c e s ,d u a sb o l a sb i e b j são retiradas de forma aleatória e seus identificadores são verificados. Se i̸ =j enã oe x i s t e aresta entre esses dois vértices, uma aresta então será inserida. Esse processo é repetido, até que não exista nenhuma bola na urna ou não seja possível conectar os vértices presentes na urna. Assim, quando não for possível conectar os vértices, haverá uma diferenc ¸a entre o número de arestas do grafo original G e G R .Ad i f e r e n c ¸ap e r m i t i d ap e l op r o c e s s o poderá ser de até 0.001%,quenãocomprometeaa valiac ¸ão. Apartirdestealgoritmoforam gerados grafos aleatórios G R para cada grafo temporal G(t) analisado, nos quais as métricas também serão computadas.

Métricas

As métricas sociais escolhidas para avaliac ¸ão serão descritas, considerando os aspectos ecaracter ísticasdamobilidadedosve ículos.Quantoamobilidade dos veículos, pode-se classificar as características em macroscópicas e microscópicas [START_REF] Uppoor | Insights on metropolitan-scale vehicular mobility from a networking perspective[END_REF]. Nesse contexto, o trabalho estende essa classificac ¸ão paraasmétricassociais,dividindoas de acordo com o que cada uma representa no grafo. As métricas macroscópicas representam medidas do estado global da rede, as quais podem retratar um comportamento geral de todos os veículos e da evoluc ¸ão do grafo temporal.A sm é t r i c a sm i c r o s c ó p i c a s definem valores individuais os veículos, representando o comportamento de um único veículo. Para as métricas macroscópicas foram escolhidas a Distância, a Densidade, o Diâmetro e a Persistência das Arestas. Como métricas microscópicas foram selecionadas oGraudoVértice,oCoeficientedeAgrupamentoeCentralidade de Proximidade. Todas as métricas escolhidas são conhecidas na literatura e comumente utilizadas em trabalhos de avaliac ¸ão de aspectos sociais em grafos.

Métricas Macroscópicas

Distância: esta é uma métrica que compreende o tamanho do caminho entreu mp a rd e veículos, em termos do número de saltos necessários. Em redes veiculares, a distância pode representar a existência de um interesse comum entre condutores. Se a distância entre os veículos v i e v j é g r a n d e , i s t o i m p l i c a e m d i z e r q u e e l e s e s t ã o fi s i c a m e n t e d istantes, fora do raio de alcance, e provavelmente não visitam lugaresp ró x i mo s . C a s oc o n t rá r i o , se a distância é pequena, v i e v j podem visitar lugares próximos ou possuem pontos em comum ao longo de sua rota. Geralmente, grafos com o comportamento de small world possuem curta distância.

Diâmetro: pode-se definir o diâmetro de um grafo como a maior distânciaentrequaisquer pares de nós. Considerando as redes veiculares, um grafo comm u i t o sv e í c u l o seu m pequeno diâmetro, pode indicar existência de pontos de interesse em comum entre esses veículos ou também a possibilidade de engarrafamentos. Emc o n t r a p a r t i d a ,u mg r a n d e diâmetro pode indicar a não existência de similaridade nar o t i n ad o sm o t o r i s t a s . A lé m disso, um diâmetro maior pode acarretar o custo na comunicac ¸ã o , c o m m a i s a t r a s o s e n t r e aorigemeodestino,devidoàquantidadedesaltosqueainformac ¸ão fará.

Densidade: representa o quão densa é a rede, isto é, a quantidade de conexões existentes entre os veículos. No contexto das redes veiculares, regiões urbanas podem ter uma alta densidade que regiões periféricas ou rurais. Em grandes centros urbanos, a densidade tende a ser elevada devido ao tráfego lento e a existência deengarrafamentos.Estamétrica pode ser computada pela razão entre o número de arestas existentes no grafo e(t) eo número de arestas de um grafo completo |V ||V -1|/2.

Persist ência de Arestas: é u m a m é t r i c a q u e r e p r e s e n t a a p e r s i s t ê n c i a d e u m e n c o n t r o entre dois veículos. Esta análise considera persistência de arestas o número de vezes que ov e í c u l ov i e v j se encontram durante o tempo. Para isso, computa-se essa métrica em func ¸ão do peso da aresta que representa o número de vezes que o encontro e ij (t) acontece.

Métricas Microscópicas

Grau do Vértice: determinar o número de encontros distintos que um veículo teve durante um período. Esta métrica pode ser influenciada pela trajetó r i a d o v e í c u l o e p e l o p e r í o d o d o dia. Se um veículo cruza uma região de alta densidade ou em horário de pico, o seu grau tende a ser elevado. De outra forma, em regiões afastadas do centro da cidade ou em horas de baixo tráfego, o grau pode ser baixo e até nulo. Como uma definic ¸ão formal, o grau de um veículo v i no tempo t pode ser definido pela expressão: Grau i (t)=||{v j |∃e ij (t)}||.

Coeficiente de Agrupamento (cluster coefficient): esta métrica pode avaliar o quão próximo estão os vizinhos de um veículo v i no grafo, isto é, a probabilidade que dois vizinhos do veículo v i tem de se encontrem. Esta métrica pode representar regiõesd e engarrafamento, quando o coeficiente é alto. Além disso, searedeapresentaofenômeno small world,seucoeficientedeagrupamentodeveserelevado [W attsandStrogatz 1998].

Centralidade de Proximidade (closeness centrality): esta métrica mensura a centralidade de um veículo em relac ¸ão a sua distância para os demais veí c u l o s d o g r a f o . O q u ã o m a i s central for o veículo, menor será a sua distância para os demais. Apesar de ser uma métrica global, seu valor também pode representar a centralidade da rota de um veículo em relac ¸ão aos demais. Possivelmente, veículos que trafegam mais em áreas centrais tendem a ter um valor baixo de centralidade.

Resultados

Esta sec ¸ão apresenta os resultados da análise efetuada sob as bases de dados. A Sec ¸ão 4.1 descreve as características de cada base de dados avaliada.A S e c a o 4 . 2 a p r e s e n t a o s resultados para as métricas macroscópicas e a Sec ¸ão 4.3 apresenta os resultados para as métricas microscópicas de acordo com a definic ¸ão na Sec ¸ã o 3 . 3 .

Traces Avaliados

Foram analisadas duas bases de dados públicos (traces), que descrevem a mobilidade de veículos. A primeira base de dados é uma base realística, no qual os dados foram gerados baseados em modelos matemáticos que consideram informac ¸õ e s d e t r á f e g o d a c i d a d e d e Zurich [START_REF] Naumov | An evaluation of inter-vehicle ad hoc networks based on realistic vehicular traces[END_REF]]. Esta base de dados representa a evoluc ¸ão do tráfego urbano durante um dia, incluindo a variac ¸ão de horários de pico e madrugadas. São informac ¸ões geradas por um simulador, e contém detalhes de destinos dos veículos e a velocidade empregada para efetuar o trajeto. Pode-se ver essa variac ¸ão do tráfego na Figura 1-(a). Nota-se que existem dois intervalos de tempo os quais apresentam uma grande quantidade de veículos, chamados de horários de pico: 6 -9am e 2 -5pm. Toda a base de dados descreve o movimento de 260.000 veículos, com a concentrac ¸ão de veículos nos horários de pico: Entretanto, durante os finais de semana o decaimento da quantidade de táxis em circulac ¸ão é menor. Isso pode ser atribuído ao fato das pessoas permanecerem na rua até mais tarde, tendo mais eventos noturnos. Durante a semana é possível verificar o início das jornadas diárias de circulac ¸ão dos veículos, com o crescimento da curva a partir das 6am. Além disso, percebe-se um comportamento constante na quantidade de veículos, com mais de 400 táxis em circulac ¸ão durante todo o dia. Devido a esse comportamento, nesta base, as métricas foram calculadas considerando os cenários: dias da semana e finais de semana. Nas sec ¸ões a seguir serão apresentados os resultados numé r i c o s p a r a c a d a m é t r i c a avaliada em cada uma das bases de dados. Com o efeito de comparac ¸ão, deve-se lembrar de que alguns resultados serão apresentados com o seu valor correspondente computado para grafos aleatórios. Esses grafos foram gerados com o mesmo número de vértices e a mesma distribuic ¸ão de graus para cada período do dia.

Métricas Macroscópicas

Nesta sec ¸ão serão descritos os resultados para as métricas que retrata a estrutura global do grafo, e que no contexto veicular, conseguem capturar informac ¸ões de como o comportamento de todos os veículos pode influenciar nessa estrutura e por consequência na mobilidade.

Distância:

Ao analisar a distância entre dois vértices num grafo, é importante lembrar neste caso que adistânciaconsideraonúmeromédiodearestasqueconectam dois vértices, sem considerar o peso das arestas. Numa rede veicular, esta métrica poderepresentarsedoisveículos frequentam ou não o mesmo lugar, isto é, veículos que possuem rotinas similares tendem a apresentar distância curta entre eles. Em compensac ¸ã o , v e í c u l o s q u e t r a n s i t a m e m horários diferentes, ou atravessam regiões distantes, tendem a possuir longas distâncias para os demais. O gráfico na Figura 2 apresenta a média da distância para as duas bases analisadas.

Na Figura 2-(a) verifica-se a distância na base de Zurich. Noshoráriosnosquais não existe tráfego a distância foi considerada 0.Entretanto,nosdemaishorárioséposs ível observar o aumento do valor da distância quando há mais tráfego. Todavia, esse aumento não é tão expressivo, pois, apesar do tráfego intenso, existem pontos congruentes de rotas nas regiões centrais, o que tende a manter o valor da distância baixo, considerando que novos encontros entre os veículos acontecerão. Ao analisar o comportamento da curva para os grafos aleatórios, é possível verificar que uma distância menor em alguns horários. Devido à forma de gerac ¸ão, a inserc ¸ão de algumas arestaspodetercriadoatalhosnografo, reduzindo a distância média entre os vértices. De diferente maneira, nas Figuras 2-(b) e 2-(c), pode-se observar o comportamento da distância para abasedeSãoFrancisco.Notase um pequeno aumento na distância no momento de pouco tráfego de táxis nas ruas.

Esse comportamento é esperado pois, com a reduc ¸ão de veículos a tendência também é reduzir os encontros, o que reflete no valor da distância. Nosdemaishorários,adistância apresenta um comportamento constante, próximo de 1.D e s t af o r m a ,ac o m p a r a c ¸ã oc o m grafos aleatórios não apresentou variac ¸ões. Para a based eZ u r i c hp o d e -s ec o n s t a t a ro fenômeno small world:u mg r a n d en ú m e r od ev é r t i c e sn og r a f oc o mp e q u e n ad i s t â n cia entre eles. Entretanto, devido a estrutura do grafo, não é possível verificar o mesmo comportamento para a base de São Francisco.

Diâmetro:

Em concordância com a métrica distância, o diâmetro do grafo consegue capturar a maior distância entre dois vértices do grafo. Desta forma, com essa métrica é possível verificar maiores detalhes da estrutura topológica do grafo e entender melhor a evoluc ¸ão da mesma. Importante lembrar que a avaliac ¸ão dessa métrica só é possível se o grafo for conexo. Caso contrário, o diâmetro representará a maior distância entre dois vértices, dentre os componentes do grafo. Para as redes veiculares, um grafo G(t) com muitos vértices e um diâmetro pequeno pode indicar a ocorrência de engarrafamentos, ou mesmo a existência de uma grande similaridade de rotas entre os veículos para o instante analisado. Neste contexto, um grafo G(t) com poucos vértices e um grande diâmetro, pode indicar a existência de tráfego periférico com veículos possuindo rotas com poucos encontros e pouca similaridade de comportamento. Além disso, ao considerar o custo de comunicac ¸ão, um grande diâmetro pode acarretar num aumento de custo para transmissão, sendo necessário mais saltos para a informac ¸ão alcanc ¸ar o destino. AF i g u r a3a p r e s e n t aae v o l u c ¸ã od ov a l o rd od i â m e t r od u r a n te o dia. Pode-se observar para a base de Zurich (Fig. 3-(a)) que o valor diâmetro sofre uma reduc ¸ão nos horários de pico. Isso ocorre, pois nestes horários os encontros nas regiões centrais são mais frequentes. Para a base de São Francisco (Fig. 3 (c) apresenta respectivamente a evoluc ¸ão para os dias da semana e finais de semana. Nota-se que durante o dia a densidade permanece superior a 80% eduranteamadrugadaessevalorreduzpara60%.I ssooc or r e pois o número de viagens feitas por um táxi durante o dia é maior e também, por haver um maior número de táxis em circulac ¸ão, a probabilidade de ocorrer encontros é maior. Em contrapartida, na madrugada, pela reduc ¸ão de táxis em circulac ¸ão e a própria ociosidade de corridas neste horário, contribui para a reduc ¸ão da quantidade de encontros. Quando se compara os dois gráficos, nota-se uma pequena diferenc ¸a na densidade entre os dias da semana e os finais de semana. Essa diferenc ¸a pode ser atribuída à escolha de destinos nos finais de semana. Por serem destinos mais variados, a tendê n c i a é q u e o c o r r a u m a reduc ¸ão na probabilidade de encontro entre os táxis. 

Persistência de Arestas:

Neste trabalho, persistência de arestas descreve a quantidade de vezes que o par de ares-tas de repete ao longo do tempo, ou seja, se um encontro entre dois veículos se repete. Entretanto, devido as diferentes durac ¸ões das bases de dados, avaliamos a persistência de duas formas. No cenário de Zurich, a persistência é mensurada considerando os horários de pico, nos quais a concentrac ¸ão de veículos é maior. Desta forma foi possível capturar os encontros que acontecem no início do dia e que se repetem nofi n a ld od i a . P a r ao trace de São Francisco, consideramos a persistência dia-a-dia, no mesmo horário. Com aa v a l i a c ¸ã od e s s amé t r i c a ,of o c oév e r i fi c a rn a sd u a sb a s es de dados a porcentagem de veículos que possuem o comportamento similar, isto é, passam pelos mesmos locais e se encontram com frequência.

Para a base de dado de Zurich, no início do dia (6 -9am.), o grafo possui 376.245 arestas e no final do dia (2 -5pm.) o grafo possui 338.513 arestas. A persistência de arestas para esta base foi de 43% das arestas, isto é, aproximadamente 150.000 arestas se repetem, o que indica uma parte expressiva de veículos temoc o m p o r t a m e n t os e m elhante na cidade, com a mesma rotina. Para a base dados de São Francisco também foi considerado os horários de maior quantidade de veículos emc i r c u l a c ¸ã o ,q u ec o m e c ¸aa acontecer a partir das 6am. Nesse momento, a quantidade de veículos permanece superior a 400 táxis e a quantidade de arestas em média no grafo é de 60.000 arestas. Assim, com ap o r c e n t a g e md e75%,ap e r s i s tê n c i ad ea r e s t a sp a r aab a s ed eSã oF r a n c i s c oém aior. Apesar de serem veículos que trafegam para destinos diversos, táxis tendem a voltar para os e up o n t od ep a r t i d a ,n oq u a la g u a r d a mn o v o sp a s s a g e i r o s . A lém disso, esses pontos normalmente são fixos, o que aumenta a probabilidade de encontrar os mesmos veículos. Este é um bom indicativo para comprovar a existência de comportamento social no grafo etambémqueasrotinasexercemumaforteinfluêncianadefinic ¸ão do tempo de viagem e nas trajetórias.

Métricas Microscópicas

Grau do Vértice:

Quando avaliamos o grau do vértice numa rede veicular, é importante lembrar que durante o dia a densidade de tráfego sofre variac ¸ões e consequentemente a quantidade de encontros que um veículo faz é influenciada pela quantidadedev e íc ulose mc ir c ula c ¸ã o. OgráficonaFigura5representaaevoluc ¸ãodograudosvértices para a base de dados de Zurich. Nota-se na Figura 5-(a), que o valor do grau acompanhaaocorrênciadoshorários de pico, e observa-se também um aumento para o grau médio, mediano e máximo. Durante os horários de pico, como às 7am., é o momento de maior valor para o grau 1.355,o que representa a existência de veículos que fazem viagens em regiões com alta densidade de tráfego e que fazem viagens maiores. O mesmo comportamento pode ser observado durante às 3pm. com altos valores de grau. Contudo, o valor do grau medianotambém apresenta um pequeno aumento, acompanhando o aumento de tráfego, com valores de 200 para o grau em horários de pico. Estes são valores aceitáveis, pois com o aumento de tráfego é esperado a ocorrência de mais encontros.

Muitas redes sociais são consideradas como livres de escala, e uma das características destas redes é que a sua distribuic ¸ão de grausse gueumaleidepotência[Ne wman 2005], poucos vértices com grau alto e muitos vértices com grau baixo. Nas 

Coeficiente de Agrupamento:

Oc o e fi c i e n t ed ea g r u p a m e n t oéu m amé t r i c am u i t oi m p o r t a n t ep a r aa ná l i s en u m ar e d e social, pois com essa métrica é possível mensurar a organizac ¸ão do grafo e mensurar oq u ã op r ó x i m oo sv i z i n h o se s t ã od eu mv e í c u l o . N oc o n t e x to de uma rede veicular, oc o e fi c i e n t ed ea g r u p a m e n t op o d er e p r e s e n t a ro sv e í c u l o sn am e s m ad i r e c ¸ã o ,q u et e m interesses em comum ou que passam pelo mesmo lugar com frequência, isto é, um grupo de veículos que encontram em algum ponto da trajetória. A Figura 8 apresenta o valor para o coeficiente de agrupamento máximo, médio e mediano e asuadevidacomparac ¸ão com os grafos aleatórios durante o dia. Nota-se na Figura 8-(a) que o valor máximo do coeficiente de agrupamento é 100%s durante todo o tempo dos horários de tráfego intenso, oquerepresentaquenesteperíodoexistemveículosquepossuem todos os seus vizinhos conectados entre si.

Quando existem muitos veículos em circulac ¸ão na cidade, principalmente nas á r e a s c e n t r a i s , p o d e a p a r e c e r m u i t o s p o n t o s d e e n g a r r a f a m ento, principalmente em avenidas as quais recebem fluxos de várias ruas adjacentes. Nestas regiões, existe uma tendência forte de formac ¸ão de agrupamentos de veículos, que compartilham as mesmas rotas e condic ¸ões de tráfego. Ainda na Figura 8-(a) pode-se observar que o coeficiente de agrupamento médio é 50%,ouseja,metadedosvizinhosdeumveículotiveramencontro em algum momento durante sua trajetória. Quando se compara com grafos aleatórios, é possível perceber que a base de dados de Zurich apresenta um coeficiente uma ordem de grandeza maior do que os grafos aleatórios, o que nos leva ac o n s t a t a rq u ee s s ab a s e apresenta fortes indicativos de comportamentos sociais, com a formac ¸ão de comunidades [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]]. 

Conclusões e Trabalhos Futuros

Neste trabalho foi apresentada uma análise social para duasb a s e sd ed a d o sc o n h e c i d a s na literatura, a base de Zurich e a base de São Francisco. Sãod u a sb a s e sq u ep o s s u e m comportamentos e rotinas diferentes. A primeira representaotráfegodeveículospessoais numa região de grande cidade e a segunda base um conjunto de tá x i s s e d e s l o c a n d o p a r a atender passageiros, também numa grande cidade. A análisedabasededadosdeZurich apontou fortes características sociais, como a presenc ¸a de comunidades comprovada pela métrica coeficiente de agrupamento e as distâncias curtas entre os vértices no grafo. Podese comprovar também a existência de interesses comuns e rotinas nesta base. Entretanto, a base de São Francisco, por apresentar movimentos de veículos de mesma natureza (táxis), em regiões próximas, apresentou uma grande densidade de encontros, com a estrutura bem próxima de um grafo completo. Constata-se também nessab a s eq u ead i v e r s i d a d e de destinos de um táxi e o seu constante deslocamento diário, deixa-o mais suscetível a encontrar outros veículos. Essas características reforc ¸a m a i d e i a q u e a a n á l i s e d e u m t r a c e sob a perspectiva social deve considerar as peculiaridades da cidade, dos tipos de veículos eose upa drã odemobilida de . C ontudo,a oa na lisa rr otina sepadrões de mobilidade de veículos, é importante ressaltar que a existência de similaridade nas rotas deve considerar toda a rotina de um condutor e a sua interac ¸ão com os demais, durante todo o seu trajeto.

Como trabalhos futuros, pretende-se analisar outras bases,a l é md ec a r a c t e r i z a r essa mobilidade em func ¸ão de tempo e espac ¸o, tentando quantificar diferenc ¸as entre as métricas por regiões numa cidade. Além disso, almeja-se or e fi n a m e n t od e s t aa n á l i s e , com a variac ¸ão dos parâmetros utilizados na construc ¸ãodosgrafosea v aliac ¸ãodeoutras métricas. Outro ponto importante a investigar é a aplicac ¸ãodessasmétricasparamelhorias de protocolos em redes veiculares. Protocolos de disseminac ¸ã o d e d a d o s p o d e m f a z e r uso de métricas sociais para alcanc ¸ar melhorias na cobertura e reduc ¸ão do número de transmissão. Além disso, métricas que quantificam interesses comuns podem ser úteis na disseminac ¸ão de propagandas e informativos na rede. Destaf o r m a ,p r e t e n d e -s ea p l i c a r conceitos sociais no desenvolvimento de protocolos de roteamento em redes veiculares.

  ]. Entretanto, em redes veiculares, as análises sociais podemserusadasparamonitorar a evoluc ¸ão do tráfego durante o dia, objetivando o conhecimento das rotinas dos usuários, identificando trajetórias similares e horários de pico. O objetivo dessas análises é m e l h o r a r e a d a p t a r o s s e r v i c ¸o s p r o v i d o s n e s t e t i p o d e r e d e. Considerando o comportamento social, em [Fiore and Härri 2008], Fiore et al. apresentam uma análise detalhada das propriedades topológicas de uma rede veicular. Os autores usam métricas sociais para investigar a evoluc ¸ão temporal da topologia da rede. Resultados mostraram que é possível tirar vantagem da mobilidade veicular para melhorar o desempenho dos protocolos de rede. Contudo, os autores efetuam a análise se baseando apenas em modelos de tráfego analíticos, conhecidos na literatura.

  Ografoentãoédefinidoconsiderandoosencontrosqueaconteceram hora-a-hora. Ografonoinstantet é u n i d i r e c i o n a l e p o d e s e r d e fi n i d o c o m o u m g r a f o G(t)=( V, E), onde V representa o conjunto de veículos com todos veículos v i e E representa o conjunto de arestas. O grafo G é t e m p o r a l , n o q u a l u m a a r e s t a e ij (t) existe entre dois veículos v i e v j somente durante o tempo t,comi̸ =j.T o d a sa smé t r i c a sf o r a ma v a l i a d a sd eh o r ae m hora, considerando o grafo tempo G(t).

  173.470 veículos às 7am, e 132.633 veículos às 3pm. Essa base de dados foi analisada considerando todo o dia, com o destaque para os horá r i o s d e p i c o , d e a c o r d o com cada métrica. Asegundabasededadosavaliadaéumabasereal,quecontémoregistrodemobilidade de 551 táxis na cidade de São Francisco (EUA) durante quatro semanas [Piorkowski et al. 2009]. São registros reais, coletados por dispositivos GPS localizados em cada veículo, minuto-a-minuto, durante sua trajetória. Ép o s s í v e lo b s e r v a rad i s t r i b u i c ¸ã od e veículos durante os dias da semana e finais de semana, respectivamente, nas Figuras 1-(b) e1 -( c ) .P o d e -s e v e r i fi c a r n o s d o i s g r á fi c o su m t r á f e g o m e n o sintensoduranteamadrugada.

Figura 1 .

 1 Figura 1. Distribuic ¸ão do Tr áfego durante o dia.

Figura 2 .

 2 Figura 2. Evoluc ¸ão da Dist ância durante o dia.

  -(b) e 3-(c)) pode-se observar um comportamento semelhante com o aumento do diâmetro nos horários de reduc ¸ão de tráfego. Nesse período, com a reduc ¸ão do trânsito de veí c u l o s n a s r u a s , a p r o b a b i l i d a d e de encontro também reduz e a distância entre os mesmos se torna maior.

  Figura 3. Evoluc ¸ão da Di âmetro durante o dia.

Figura 4 .

 4 Figura 4. Evoluc ¸ão da Densidade durante o dia.

  Figuras 5-(b) e 5(c) pode-se observar essa distribuic ¸ão parao sd o i sh o rá r i o sc o mm a i o r fluxo de veículos às 7am. e 3pm. em escala logarítmica. Nestes horários, encontra-se

Figura 5 .

 5 Figura 5. Evoluc ¸ão do grau do v értice durante o dia.

Figura 6 .

 6 Figura 6. Evoluc ¸ão do Grau do V értice durante o dia.

Figura 7 .

 7 Figura 7. Evoluc ¸ão do Grau do V értice para diferentes hor ários.

Figura 8 .

 8 Figura 8. Evoluc ¸ão do Coeficiente de Agrupamento para a base de Zurich.

  Figura 9. Evoluc ¸ão do Coeficiente de Agrupamento para a base de S ão Francisco.

Figura 10 .

 10 Figura 10. Evoluc ¸ão da Centralidade de Proximidade durante o dia.