info.info-mc
Davidysson A Alvarenga 
email: davidysson@ufmg.br
  
Felipe D Cunha 
email: fdcunha@dcc.ufmg.br
  
Aline C Viana 
email: aline.viana@inria.fr
  
Raquel A F Mini 
email: raquelmini@pucminas.br
  
Antônio A F Loureiro 
email: loureiro@dcc.ufmg.br
  
  
  
Classificando Comportamentos Sociais em Redes Veiculares

Vehicular networks are networks comprised by vehicles traveling cities and highways. During their trajectories, these vehicles interact with other vehicles in order to make safer and enjoyable traffic. These interactions may be influenced by several factors. To mention a few: vehicle speed, roads condition and time of day. Moreover, driver behavior and its interests can influence in many vehicle features. In this context, the Vehicular Social Networks arise as a new perspective to vehicular networks. These are networks in which vehicles "socialize" and share common interests. In this work, we evaluate the behavior of vehicles in two mobility scenarios, in order to classify them according to the interactions performed, identifying common interests and similar routines. Thus, we use metrics of complex networks and statistical techniques. Results prove the existence of routines and human features in Vehicular Networks.

Introduc ¸ão

Redes Veiculares (Vehicular Networks -VANETs) são um tipo de rede formadas por veículos, que interagem entre si diretamente ou por meio de infraestrutura instaladas nas vias públicas. Esses veículos possuem capacidade de processamento, comunicac ¸ão e sensoriamento. No entanto, devido à grande mobilidade dos veículos, estas redes possuem uma alta variac ¸ão na sua topologia. Outros fatores que cooperam para esta variac ¸ão são os limites de velocidade e direc ¸ão impostos aos veículos pelas vias públicas.

Durante suas trajetórias os veículos interagem entre si, e diversos fatores podem influenciar nestas interac ¸ões. Dentre eles podemos citar: o horário do dia, a velocidade dos veículos, o local, engarrafamentos, a existência de eventos, etc. Por exemplo, em horários de pico (tráfego denso), as vias públicas podem ser vistas como um lugar popular, onde é mais suscetível ocorrer interac ¸ões. Outro fator que pode influenciar nas interac ¸ões é o comportamento do condutor e seus interesses comuns com outros condutores. Este traz consigo uma nova perspectiva para as redes veiculares: as Redes Sociais Veiculares (Vehicular Social Networks -VSNs) [START_REF] Vegni | A survey on vehicular social networks[END_REF].

Neste contexto, este trabalho se propõe a investigar as VSNs, estudando a influência do comportamento humano na mobilidade veicular, identificando padrões, rotinas semelhantes e interesses comuns. Além disso, pretende-se discutir as melhorias que esse conhecimento pode oferecer no estabelecimento das redes veiculares. Para isso, foram analisadas duas bases de dados de veículos usando métricas de redes complexas e técnicas estatísticas. Os resultados apontam que é possível identificar classes de comportamentos nas redes sociais veiculares.

O restante do trabalho está organizado da seguinte forma: a Sec ¸ão 2 apresenta um breve resumo dos trabalhos relacionados encontrados na literatura. A Sec ¸ão 3 descreve a metodologia utilizada neste trabalho, as bases de dados selecionadas e as métricas e técnicas utilizadas. A Sec ¸ão 4 apresenta os resultados quantitativos, de acordo com cada métrica avaliada. A Sec ¸ão 5 discute sobre como aplicar estas métricas na elaborac ¸ão de novos servic ¸os para VANETs. Finalmente, a Sec ¸ão 6 apresenta as conclusões e as perspectivas futuras.

Trabalhos Relacionados

Estudos recentes tem comprovado a influência do comportamento humano na mobilidade dos veículos [START_REF] Fiore | The networking shape of vehicular mobility[END_REF][START_REF] Liu | Exploring social properties in vehicular ad hoc networks[END_REF][START_REF] Cunha | How effective is to look at a vehicular network under a social perception? In Wireless and Mobile Computing, Networking and Communications[END_REF]. Nesses estudos pode-se averiguar como as interac ¸ões ocorrem entre os veículos, a frequência dessas interac ¸ões, os horários de maior probabilidade de ocorrência e também como utilizar melhor essas interac ¸ões em projetos de novos servic ¸os e aplicac ¸ões para redes veiculares.

Normalmente esses estudos se apoiam na teoria de redes complexas, na análise de traces de mobilidade de veículos e em técnicas estatísticas [START_REF] Francisco | Caracterizac ¸ão, classificac ¸ão e análise de redes complexas[END_REF]. Assim, os autores exploram a avaliac ¸ão das métricas em grafos que representam contatos entre os veículos numa determinada janela de tempo de avaliac ¸ão. A Tabela 1 apresenta os trabalhos que caracterizaram cenários de mobilidade veicular e que buscam entender melhor a evoluc ¸ão topológica da rede.

Pode-se observar que em [START_REF] Fiore | The networking shape of vehicular mobility[END_REF][START_REF] Rezende | The impact of mobility on mobile ad hoc networks through the perspective of complex networks[END_REF][START_REF] Monteiro | Improving vanet protocols via network science[END_REF], os autores avaliaram apenas pequenos cenários analíticos, nos quais foram utilizados geradores sintéticos de mobilidade. De forma mais ampla, o comportamento urbano das grandes cidades foi estudado em [START_REF] Pallis | On the structure and evolution of vehicular networks[END_REF][START_REF] Uppoor | Insights on metropolitan-scale vehicular mobility from a networking perspective[END_REF][START_REF] Naboulsi | On the instantaneous topology of a large-scale urban vehicular network: the cologne case[END_REF], nos quais os autores avaliaram as características da mobilidade realística dos veículos que circulam dentro de alguns municípios.

Por outro lado, em [START_REF] Loulloudes | The dynamics of vehicular networks in urban environments[END_REF][START_REF] Liu | Exploring social properties in vehicular ad hoc networks[END_REF] os autores estudaram cenários com a mobilidade de táxis reais em algumas cidades, extraindo propriedades e comportamentos da rede. Entretanto, por questões de privacidade, na literatura não se encontra dados reais de veículos particulares, o que pode impossibilita uma melhor extrac ¸ão de comportamentos humanos. Desta forma, em [START_REF] Gautam S Thakur | The structure and traffic flow anatomy of the planet-scale urban vehicular mobility[END_REF], os autores constroem e analisam a estrutura da rede utilizando fotografias de algumas regiões das cidades. Contudo, parte destes trabalhos apresentam algumas limitac ¸ões. Alguns não analisaram as bases em sua plenitude, uma vez que isolaram a área central das cidades, ignorando as regiões periféricas. Outros computaram poucas métricas, não relacionando os resultados com outros modelos. Estudos recentes mostraram que, com a análise de todas essas bases de dados, é possível encontrar características humanas no comportamento dos veículos [START_REF] Cunha | How effective is to look at a vehicular network under a social perception? In Wireless and Mobile Computing, Networking and Communications[END_REF][START_REF] Cunha | Is it possible to find social properties in vehicular networks?[END_REF]. Apesar destas análises estarem apoiadas em bases de dados de táxis ou mesmo em bases sintéticas, foi possível verificar a existência de interesses comuns e comportamentos similares em uma rede veicular. Esses comportamentos reforc ¸am a ideia das Redes Sociais Veiculares [START_REF] Vegni | A survey on vehicular social networks[END_REF], redes nas quais os veículos interagem, compartilham interesses comuns e comportamentos semelhantes.

Metodologia

Nesta sec ¸ão serão apresentados os detalhes de toda a metodologia utilizada na avaliac ¸ão das bases de dados. O foco dessa avaliac ¸ão é entender melhor como acontecem as interac ¸ões entre os veículos, destacando os comportamentos e as características sociais dos mesmos. Em primeiro momento, será descrito os detalhes das bases de dados avaliadas. Em seguida, será descrito o processo de gerac ¸ão dos grafos e as métricas utilizadas.

Bases de Dados Avaliadas

A selec ¸ão das bases de dados utilizadas neste trabalho foi definida por critérios que envolveram: mobilidade diversificada ao longo das 24 horas do dia, registros em mais de um dia da semana, granularidade semelhante, quantidade semelhante de veículos em circulac ¸ão por faixas horárias e disponibilidade pública. A primeira base de dados foi obtida a partir da extrac ¸ão de coordenadas de localizac ¸ão geográfica durante a simulac ¸ão de um modelo de mobilidade realística na cidade de Helsinque. A segunda base de dados contém dados reais da mobilidade de táxis dentro da cidade de Roma. • Helsinque: representa a mobilidade realística gerada pelo modelo Working Day Movement Model (WDM) [START_REF] Ekman | Working day movement model[END_REF]. Assim, a mobilidade de 2.000 pessoas foi gerada utilizando veículos diversos (carros, ônibus ou táxis), se locomovendo entre 3 locais distintos (residência, trabalho e pontos de lazer), ao longo das 24 horas do dia, dentro de um intervalo de 1 semana útil. A simulac ¸ão do tráfego foi realizada no software The ONE, utilizando os parâmetros descritos na Tabela 2. • Roma: esta base de dados contém a mobilidade real de 320 táxis que trabalham na região central da cidade. Os registros foram coletados durante 4 semanas em 2014 [START_REF] Bracciale | CRAWDAD data set roma/taxi (v. 2014-07-17[END_REF].

A Figura 1 apresenta a evoluc ¸ão do tráfego diário e semanal para as duas bases. É possível observar um trânsito maior durante os horários de pico, com uma reduc ¸ão no horário de almoc ¸o e nas madrugadas. Além disso, para a base de Helsinque é possível verificar que não existe tráfego durante os finais de semana. Este é um modelo que considera apenas dias úteis, desprezando finais de semana e feriados. Ao olhar para o tráfego semanal em Roma, nota-se uma reduc ¸ão aos finais de semana, o que pode ser explicado pelo contexto dos dias.

Analisando a evoluc ¸ão do tráfego sob as cidades, a Figura 2 apresenta o heatmap do tráfego. Pode-se destacar Roma, onde às 6 am. o tráfego é bem esparso, e o mesmo apresenta-se muito mais denso às 6 pm, onde os veículos passam a utilizar vias paralelas aos congestionamentos. Além disso, nota-se que as duas cidades possuem características de tráfego bem distintas para os mesmos horários do dia. Esse é um comportamento que indica características peculiares em cada cidade, e que as mesmas devem ser consideradas no projeto de soluc ¸ões para essas redes. 

Grafos Temporais

Um grafo temporal no tempo t é um grafo não dirigido, definido como um grafo G(t) = (V, E), onde V representa o conjunto com todos os veículos V i e E representa o conjunto de arestas E ij . Em G(t), existe uma aresta E ij (t) entre os veículos V i e V j durante o tempo t, se i 6 = j. A avaliac ¸ão de cada métrica deve levar em conta cada um dos grafos temporais G(t), com as interac ¸ões que acontecem em cada período t. Por exemplo, se t estiver definido para 15 minutos, os registros ocorridos entre 08:00 -08:14 serão agrupados em t 0 e os registros ocorridos entre 08:15 -08:29 horas serão agrupados em t 1 .

Durante a criac ¸ão dos grafos temporais, o critério para inserc ¸ão de arestas entre dois vértices é definido pela distância entre as coordenadas dos veículos. Se essa distância for menor ou igual ao valor do raio da comunicac ¸ão, os vértices serão conectados. Todas as arestas que pertencerem ao mesmo intervalo de avaliac ¸ão serão agrupadas em um grafo G(t). Na direc ¸ão de entender melhor as características destas arestas e verificar as propriedades existentes, cada grafo G(t) será comparado a outro grafo aleatório G R gerado pelo algoritmo de urna [START_REF] Lloyd | Urn models and their application; an approach to modern discrete probability theory[END_REF], com mesma quantidade de arestas e distribuic ¸ão de graus dos vértices. Por meio deste processo, foi possível verificar a existência de estruturas sociais no grafo temporal, que é inexistente no grafo aleatório.

Métricas Avaliadas

Nesta sec ¸ão serão descritas as métricas escolhidas para avaliac ¸ão das bases de dados. Dentre as métricas conhecidas de redes complexas [START_REF] Da F Costa | Characterization of complex networks: A survey of measurements[END_REF], neste trabalho optou-se por agrupá-las de forma que as métricas que representam o mesmo comportamento pertenc ¸am a mesma categoria. Assim, quatro grupos foram definidos: métricas que mensuram a influência dos vértices sob seus vizinhos, métricas relacionadas ao fenômeno "Mundo Pequeno", métricas de centralidade e métricas de semelhanc ¸a de contatos. Os valores finais de cada métrica foram calculados utilizando o valor médio observado em cada intervalo de tempo analisado.

Vértices vs. Vizinhos: O grau do vértice representa a quantidade de interac ¸ões que o mesmo faz com sua vizinhanc ¸a. Além disso, vértices que apresentam grau elevado são os mais ativos na rede, e podem atuar como um canal para a troca de informac ¸ões [START_REF] Elizabeth | Social network analysis for information flow in disconnected delaytolerant manets[END_REF]. Tal métrica pode ser vista como uma medida de centralidade, indicando a popularidade do vértice no grafo. Em um nível global, um alto grau pode indicar uma alta concentrac ¸ão de veículos próximos uns aos outros, comum em horários de pico ou engarrafamentos. Por outro lado, o grau médio dos vizinhos (average neighbor degree) representa a média dos graus de todos vizinhos que cada vértice possui. A avaliac ¸ão da sua correlac ¸ão com os graus dos vértices mostra a tendência de um vértice se ligar a outros com graus similares. Nesse sentido, a rede é considerada como assortativa quando a correlac ¸ão for crescente. Nessas redes, veículos que compartilham rotinas estarão ligados uns aos outros e com graus semelhantes [START_REF] Mark | Assortative mixing in networks[END_REF].

Outra importante métrica que se pode avaliar no contexto de comportamentos semelhantes é a presenc ¸a de comunidades no grafo. No contexto de redes veiculares, uma comunidade representa indivíduos que possuem interesses comuns. No grafo pode-se destacar um subconjunto de vértices fortemente conectados entre si. Neste trabalho, para avaliac ¸ão dessa métrica optou-se em executar o algoritmo Walktrap [START_REF] Pons | Computing communities in large networks using random walks[END_REF], aplicado em cada componente existente no grafo temporal G(t) a fim de detectar conjunto de veículos que formam as comunidades. Ao quantificar as conexões entre os veículos, pode-se avaliar também a densidade de arestas no grafo. Essa pode apresentar valores elevados em regiões urbanas em relac ¸ão às áreas periféricas ou rurais, devido ao tráfego lento ou à existência de engarrafamentos. Valores baixos de densidade ajudam a identificar regiões cuja conectividade pode ser interrompida mais facilmente, exigindo estratégias que busquem minimizar tal problema.

Centralidade: A centralidade de um vértice no grafo indica o quão importante aquele vértice é em relac ¸ão aos demais. Do ponto de vista de distância e comunicac ¸ão, o quão mais central um vértice for, mais caminhos mínimos passarão por ele e mais comunicac ¸ões o mesmo irá intermediar. Uma forma de definir essa centralidade é a métrica centralidade de intermediac ¸ão (beetweeness centrality), que representa a frequência com que um veículo faz parte de um caminho mais curto entre quaisquer dois outros veículos. Essa métrica é importante em situac ¸ões nas quais dois vértices não são vizinhos e dependem dos outros vértices para realizar sua troca de dados. A posic ¸ão da intermediac ¸ão indicará a influência do vértice ao levar em considerac ¸ão o controle exercido por ele sobre as interac ¸ões entre os dois outros.

Mundo Pequeno: O fenômeno "mundo pequeno" (small-world) [START_REF] Milgram | The small world problem[END_REF] define a premissa que qualquer pessoa pode se conectar à outra por meio de uma sequência de relacionamentos em um grau médio de 5 a 6 pessoas [START_REF] Milgram | The small world problem[END_REF][START_REF] Duncan | Collective dynamics of small-world networks[END_REF], o que numa rede representaria o número de conexões que separam duas pessoas. Além disso, redes que apresentam esse fenômeno possuem uma grande tendência de formar comunidades, ou seja, formar agrupamentos de nós que compartilham interesses comuns. Para avaliar e classificar uma rede como "mundo pequeno" utiliza-se as métricas coeficiente de agrupamento e a distância média. Assim, essas redes tendem a apresentar uma distância média baixa e um elevado coeficiente de agrupamento. A distância média representa o número de saltos necessários para a conexão entre um par quaisquer de veículos. Valores altos podem indicar atrasos em transmissões de dados, pois os veículos estão fisicamente distantes, fora do raio da comunicac ¸ão, e provavelmente não visitam locais próximos. Por outro lado, valores baixos indicam lugares próximos ou pontos em comum em suas rotas, podendo representar interesses comuns. Considerando o coeficiente de agrupamento, nas redes veiculares, os veículos que possuem interesses comuns tendem a ficar mais agrupados, o que contribui para um aumento no valor do coeficiente de agrupamento.

Semelhanc ¸a de Contatos: No contexto das redes sociais veiculares, a semelhanc ¸a de contatos pode ser avaliada por duas métricas: a sobreposic ¸ão topológica e a persistência de arestas. A sobreposic ¸ão topológica (topological overlap) retrata a tendência de existir vértices com vizinhos partilhados, enquanto que a persistência de arestas (edge persistence) define o número de vezes que dois vértices se encontram na mesma janela temporal, ao longo do período. Esta métrica permite identificar as relac ¸ões regulares entre entidades. De acordo com [START_REF] Pedro | Recast: Telling apart social and random relationships in dynamic networks[END_REF], a avaliac ¸ão destas métricas permite a classificac ¸ão das interac ¸ões em quatro tipos de relacionamentos. Essa classificac ¸ão baseia-se na comparac ¸ão com grafos aleatórios, de forma que é possível quantificar se os relacionamentos em uma rede veicular são aleatórios ou obedecem a um padrão. Como observado na Tabela 3, na classe de Amigos (friends), são encontradas características sociais sobre rotinas semelhantes entre os veículos tanto na persistência de arestas quanto na sobreposic ¸ão topológica. Na classe de Conhecidos (acquaintance), essa característica é encontrada somente na sobreposic ¸ão topológica. Na classe de Pontes (bridges), a característica social é encontrada somente na persistência de arestas. E finalmente, na classe Aleatória (random), não há presenc ¸a de tais características nas duas métricas. 

Resultados

Nesta sec ¸ão serão apresentados os resultados da análise efetuada sobre as bases de dados. Para essa análise foi considerada a metodologia e as métricas definidas na Sec ¸ão 3. Primeiramente, a Sec ¸ão 4.1 define os parâmetros e detalhes da análise. Em seguida, os resultados serão apresentados de acordo com as propriedades definidas na Sec ¸ão 3.3.

Parâmetros

A análise dos dados foi efetuada considerando os valores ao longo do dia e da semana. O objetivo principal desta análise é identificar comportamentos e propriedades que descrevem rotinas e interesses dos condutores numa rede veicular. A partir desse entendimento será possível propor servic ¸os e protocolos que atendam melhor a demanda dos seus usuários.

Com o intuito de verificar o impacto da avaliac ¸ão nas interac ¸ões entre os veículos, neste trabalho o raio de comunicac ¸ão foi configurado de acordo com definic ¸ões do protocolo 802.11p. No entanto, foi avaliada uma variac ¸ão no raio da comunicac ¸ão, com valores de 100 e 150 metros, a fim de verificar o impacto nos resultados, uma vez que um incremento em seu valor pode agregar mais contatos antes inalcanc ¸áveis. Considerando a janela de tempo para agregac ¸ão de contatos, foram considerados os seguintes valores: 5, 15, 30 e 60 minutos, conforme discussões realizadas em trabalhos relacionados [START_REF] Falkowski | Observing dynamics in community structures[END_REF][START_REF] Hossmann | Know thy neighbor: Towards optimal mapping of contacts to social graphs for dtn routing[END_REF]. Ao considerar valores pequenos de janela, foi possível encontrar um grafo mais esparso com muitos componentes. Em contrapartida, janelas de tempo com grande intervalo agrupam uma grande quantidade de contatos, o que pode gerar grafos mais densos, retratando um comportamento homogêneo nas métricas. Com isso, a variac ¸ão é feita para mostrar como os resultados das métricas podem ser influenciados por tal parâmetro.

A Figura 3 apresenta o gráfico analisando o tamanho da janela versus número de componentes e densidade de arestas do grafo. É possível observar que o valor de 15 minutos apresenta uma boa proporc ¸ão de arestas e componentes no grafo. No intuito de melhor caracterizar as variac ¸ões de comportamentos, neste trabalho optou-se por definir o tamanho de 15 minutos como padrão para o tamanho da janela de tempo.

Além disso, a correlac ¸ão entre algumas métricas foi avaliada. O objetivo desta análise é identificar o quão dependente uma métrica é de outra, e se as métricas apresentam o mesmo comportamento, quando o tráfego varia. Para isso, foi utilizada a Correlac ¸ão de Pearson que mede o grau da relac ¸ão linear entre duas variáveis, indicando a direc ¸ão da correlac ¸ão dentro do intervalo de 1 a 1. Onde o valor é positivo quando uma variável aumenta junto com a outra, ou negativo, quando uma diminui à medida que a outra aumenta. Com isso, o nível da correlac ¸ão pode ser classificado por três intervalos: fraco (de 0, 0 a ±0, 3), moderado (de ±0, 3 a ±0, 7) e forte (de ±0, 7 a ±1, 0) [START_REF] Becker | The new s language[END_REF].

Vértices vs. Vizinhos

Ao avaliar o grau dos vértices, é importante verificar que essa métrica sofre variac ¸ões ao longo do dia, diante das mudanc ¸as na quantidade de veículos em circulac ¸ão. A Figura 4 apresenta o seu valor médio. Observa-se em Helsinque, Fig. 4-(a), o valor do grau médio permanece constante durante o dia e aumenta ao final, momento de maior densidade de veículos em circulac ¸ão. Em contrapartida, em Roma (Fig. 4-(b)), observa-se que o valor do grau acompanha a evoluc ¸ão do tráfego. Por serem táxis, veículos que circulam muito, os valores tendem a ser mais semelhantes. Nas duas bases, o aumento do raio da comunicac ¸ão agregou mais contatos e, consequentemente, o número médio dos graus.

Quando se analisa a correlac ¸ão entre os graus dos vértices e seus vizinhos, a Figura 5 mostra que os vizinhos dos vértices possuem graus parecidos com os graus dos vértices, uma vez que o Coeficiente de Pearson apresentou índices de forte correlac ¸ão positiva. Isso indica a presenc ¸a de comportamentos semelhantes dentro das redes, podendo classificá-las como redes assortativas. Redes nas quais os vértices possuem uma forte tendência de encontrar vértices altamente com graus semelhantes conectados entre si.

Quando se verifica a presenc ¸a de interesses comuns na rede através da busca por comunidades no grafo, a Figura 6, produzida utilizando o algoritmo Walktrap [START_REF] Pons | Computing communities in large networks using random walks[END_REF], mostra que os grafos temporais apresentam comunidades bem definidas. Quando se compara com os grafos aleatórios é possível verificar que a aleatoriedade na gerac ¸ão das arestas quebra as comunidades existentes, deixando comunidades mal definidas e vértices isolados. Grau dos vizinhos Grau dos vértices (a) Helsinque 

• •• • • • • • • • • • • • • • • •• • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 0am (r=0.
• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 0am (r=0.

Centralidade dos vértices

A centralidade de um veículo define a distância dele em relac ¸ão a sua distância para os demais veículos do grafo. O quão mais central for o veículo, menor será a sua distância para os demais. A Figura 7-(a) e (b) apresenta os valores para centralidade de intermediac ¸ão (betweenness). Pode-se observar que os valores dos grafos reais são maiores que dos grafos aleatórios, o que comprova que os grafos aleatórios descaracterizam as conexões dos grafos originais. Quando se observa o comportamento destes valores ao variar o tamanho da janela na Figura 7-(c) e (d), nota-se que valores menores para a janela de avaliac ¸ão apresentam maiores valores de centralidade. Isso ocorre, pois, com janelas menores, a rede apresenta mais desconexões e uma quantidade maior de pequenos componentes. Hora do dia Centralidade de intermediação 05min 15min 30min 60min (d) Roma 

Mundo pequeno

As Figuras 8 e 9 apresentam respectivamente os valores para distância média e coeficiente de agrupamento. Essas métricas retratam a presenc ¸a de características sociais com rotinas semelhantes e interesses em comum. Baixos valores pra distância e altos valores pra o coeficiente de agrupamento indicam que a rede apresenta o fenômeno small-world, uma vez que existem vértices que formam atalhos na rede reduzindo a média da distância global e existe presenc ¸a de comunidades formando grupos com interesses em comum.

Analisando a distância média, Figuras 8-(a) a (d), observa-se que os grafos aleatórios apresentam valores um pouco menor que as bases reais, devido à ruptura das conexões que ocorre no grafo aleatório. Ao variar o raio de comunicac ¸ão, observa-se que a existência de mais contatos não impacta no valor da distância média em nenhuma das bases. Nas Figuras 9-(a) e (b) são apresentados os valores do coeficiente de aglomerac ¸ão para Helsinque e Roma. Pode-se notar que as duas bases apresentam valores maiores quando comparados a grafos aleatórios. Nota-se também que durante as madrugadas os valores são mais altos indicando que os veículos circulam formando grupos provavelmente utilizando as mesmas vias. Pode-se observar também, nas Figuras 9-(c) e (d) a variac ¸ão dos valores de coeficiente em cada rede. Nota-se que a rede Helsinque, por representar mobilidade de um dia de trabalho apresentam valores maiores do coeficiente quando comparados com a base de Roma. Esta apresenta uma grande variabilidade de valores, alternando entre 20% a 40%. Hora do dia Coeficiente de agrupamento (c) Helsinque 16 20 Hora do dia Coeficiente de agrupamento (d) Roma Figura 9. Coeficiente de agrupamento ao longo do dia.

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 0% 20% 40% 60% 0 4 8 12

Semelhanc ¸a de contatos

A análise da semelhanc ¸a de contatos pode constatar que ambos os cenários apresentaram rotinas semelhantes e interesses em comum durante o processo de avaliac ¸ão das métricas de sobreposic ¸ão topológica e persistência de arestas, apresentadas nas Figuras 10 e 11. Os resultados obtidos na avaliac ¸ão da sobreposic ¸ão topológica nos grafos temporais foram maiores que os grafos aleatórios, da mesma forma que o coeficiente de agrupamento apresentado na Figura 9. Isso indica a existência de grupos de vértices que compartilham interesses em comum. Entretanto ao analisar a repetic ¸ão dos encontros, Fig. 11-( 

Correlac ¸ões entre métricas

Com o objetivo de verificar a correlac ¸ão entre as métricas e assim identificar métricas que possuem o mesmo comportamento, a Figura 12-(a) e (b) apresenta os resultados da correlac ¸ão de Pearson para as métricas sobreposic ¸ão topológica, coeficiente de aglomerac ¸ão, grau dos vértices e centralidade de intermediac ¸ão. Interessante observar que as métricas sobreposic ¸ão topológica e coeficiente de aglomerac ¸ão apresentam uma correlac ¸ão forte, em torno de 0.9 e 1. Ambas são métricas que retratam a presenc ¸a de interesses comuns entre os vértices, o que explica esse resultado. Entretanto, com as demais métricas a correlac ¸ão do coeficiente de clusterizac ¸ão e sobreposic ¸ão topológica é baixa.

Outra correlac ¸ão pode ser observada entre a centralidade de intermediac ¸ão e o grau do nó. De fato, quanto maior for o grau de um nó, maior também será a chance de se ter mais caminhos passando por ele. Comportamento esse explicado pelos valores de 0.7 a 0.9 de correlac ¸ão entre eles. 

Aplicac ¸ões em VSNs

Este trabalho apresenta uma análise de duas bases sociais que descrevem a mobilidade de veículos em um cenário, caracterizando-as como uma rede social veicular com o objetivo de compreender melhor as interac ¸ões entre os veículos, seus comportamentos e as rotinas dos condutores. Entretanto, esta análise foi executada considerando parâmetros e suposic ¸ões que caracterizam as interac ¸ões entre os veículos. Através destas interac ¸ões foram gerados grafos e computados métricas de redes complexas. Assim, pelos resultados foi possível identificar propriedades e características que indicam fortemente a presenc ¸a de comportamentos sociais nas redes veiculares.

Muitas são as possibilidades de aplicar essas propriedades e comportamentos no projeto de soluc ¸ões para rede veicular. No projeto de infraestrutura para a rede, pode-se fazer o uso de métricas como densidade de arestas e distância que ajudam na deposic ¸ão de ponto de acesso na direc ¸ão de melhorar a cobertura da rede. Através da densidade de arestas por região é possível identificar locais mais visitados, e pela distância média é possível mensurar a latência na transmissão. Em outra perspectiva, é possível projetar protocolos de comunicac ¸ão cientes da variac ¸ão do tráfego e da probabilidade de encontros entre os veículos fazendo uso da métrica grau dos nós [START_REF] Monteiro | Improving vanet protocols via network science[END_REF]. Esta métrica pode auxiliar na definic ¸ão da probabilidade de retransmitir o dado, o que pode garantir uma melhor cobertura.

Em outra direc ¸ão, é possível aplicar as métricas para o projeto de aplicac ¸ões que venham auxiliar os condutores durante o trajeto, tornando a viagem mais segura e agradável. Métricas como coeficiente de agrupamento e sobreposic ¸ão topológica podem ser usadas para identificar condutores com interesses semelhantes e que visitam os mesmos lugares para o projeto de aplicativos que incentivam caronas e compartilhamento de veículos. Além disso, baseado-se no histórico de visitac ¸ão será possível criar aplicativos para sugestão de destinos.

Conclusões e Trabalhos Futuros

Este trabalho apresentou uma caracterizac ¸ão de duas bases de dados que representam a mobilidade de veículos, buscando encontrar propriedades e características que retratam a interferência do comportamento humano na mobilidade veicular. A base realística representa a mobilidade de veículos pessoais sob o modelo Working Day Movement Model, e a segunda base representa a mobilidade de táxis na cidade de Roma. Esta análise foi realizada considerando os conceitos e métricas de redes complexas e técnicas estatísticas.

Durante a análise das bases, foi possível identificar características semelhantes às redes sociais. Apesar das bases serem de naturezas distintas, onde não há como fazer uma comparac ¸ão direta entre os resultados, diversas métricas analisadas mostraram a existência de grupos de veículos formando comunidades de pessoas com indícios de rotinas semelhantes e interesses comuns. Estes comportamentos podem ser explicados pela existência de veículos que frequentam os mesmos lugares nos mesmos períodos do dia. Além disso, os resultados mostraram que o cenário de mobilidade realística apresenta características de uma rede de amigos: onde há grupos de pessoas que se encontram com uma frequência. Em contrapartida, o cenário com mobilidade de táxis em Roma apresentou características de uma rede de pessoas conhecidas: onde há grupos de pessoas que compartilham interesses, mas seus encontros não são frequentes.

Em trabalhos futuros, pretende-se avaliar os resultados das interac ¸ões entre os veículos do ponto de vista espacial, explorando mais as interac ¸ões entre eles e os locais visitados. Também pretende-se avaliar outras bases com um número maior de veículos em circulac ¸ão, efetuando filtros e ajustes espaciais e temporais entre os registros, com o objetivo de possibilitar uma comparac ¸ão de bases de mesma natureza. Além disso, pretende-se incluir análises de estabilidade entre as comunidades para verificar como é o comportamento delas ao longo do tempo, gerando janelas deslizantes na agregac ¸ão de contatos temporais. Por fim, pode-se estender esse trabalho buscando aplicar o uso das métricas para o projeto de novas soluc ¸ões para redes veiculares.

Agradecimentos

Os autores agradecem CAPES, CNPq e FAPEMIG pelo apoio financeiro.

Figura 1 .

 1 Figura 1. Evoluc ¸ão do tr áfego ao longo do dia e da semana.

Figura 2 .

 2 Figura 2. Mapa de calor representando a mobilidade de veículos em hor ários de pico.

Figura 3 .

 3 Figura 3. Relac ¸ão entre densidade de arestas e componentes no grafo.

Figura 4 .

 4 Figura 4. Grau m édio dos v értices variado o raio de comunicac ¸ão.

Figura 5 .

 5 Figura 5. Correlac ¸ão entre o grau dos v értices e o grau dos vizinhos.

Figura 6 .

 6 Figura 6. Comunidades nos grafos temporais e aleat órios.

Figura 7 .

 7 Figura 7. Centralidade de intermediac ¸ão variando o tamanho da janela temporal.

Figura 8 .

 8 Figura 8. Dist ância m édia entre os v értices ao longo do dia.

Figura 12 .

 12 Figura 12. Grade de correlac ¸ões entre as m étricas.

Tabela 1. Trabalhos recentes encontrados na literatura que apresentam caracterizac ¸ão da mobilidade veicular.

  

	Autores			Traces Avaliados	Métricas Avaliadas	Observac ¸ões
	Fiore e Härri (2008)	Cenários analíticos	Durac ¸ão de encontros, densidade, grau dos vértices,	modelos distintos; raio fixo na comunicac ¸ão; não utiliza
	[9]				clusters e coeficiente de agrupamento	grafos temporais e aleatórios; área geográfica delimitada;
						durac ¸ão limitada.
	Pallis et (2009) [18]	Zurique	Grau dos vértices, durac ¸ão de encontros, diâmetro,	Varia o raio da comunicac ¸ão, não utiliza grafos temporais
					centralidade de vértices, clusters, coeficiente de agru-	e aleatórios; Avalia apenas algumas horas do dia; área ge-
					pamento, comunidades e correlac ¸ão entre as métricas	ográfica delimitada.
	Loulloudes,		Pallis	Xangai e Los Angeles	grau dos vértices, diâmetro, densidade, centralidade	Mobilidade realística em Los Angeles; não varia o raio da
	e Dikaiakos (2010)		de vértices, durac ¸ão e frequência de encontros, clus-	comunicac ¸ão; não utiliza grafos temporais e aleatórios; área
	[13]				ters, coeficiente de agrupamento e comunidades	geográfica delimitada; durac ¸ão limitada.
	Rezende et al. (2011)	Cenários analíticos	Diâmetro, coeficiente de agrupamento e grau dos	Região urbana/rodovia; densidade fixa; não varia o raio
	[20]				vértices	de comunicac ¸ão; não compara com grafos aleatórios; varia
						o tamanho da janela temporal; área geográfica delimitada;
						durac ¸ão limitada.
	Liu et al. (2012) [12]	São Francisco e Xan-	Grau dos vértices, distância média e coeficiente de	Seleciona apenas o maior componente do grafo; não varia
				gai	agrupamento	o raio da comunicac ¸ão; compara com grafos aleatórios; não
						teve avaliac ¸ão de janelas temporais.
	Uppoor, Naboulsi e	Colônia	Densidade e distribuic ¸ão de veículos, tempo de vi-	Analiza apenas sobre o tráfego de veículos; varia o raio de
	Fiore (2012-2013)		agem, distância percorrida, durac ¸ão de encontros	comunicac ¸ão; compara com grafos aleatórios; não varia o
	[23, 16]				componentes, grau dos vértices, centralidade de	tamanho da janela temporal, durac ¸ão limitada.
					intermediac ¸ão e assortatividade	
	Thakur, Hui e Helmy	Connecticut, Londres,	Coeficiente de agrupamento, densidade, grau dos	Modelagem dos grafos utilizando webcams como vértices
	(2013) [22]			Seattle, Sydney, To-	vértices e distância média	e as vias como arestas; não avalia variac ¸ão no raio de
				ronto e Washington		comunicac ¸ão; compara com grafos aleatórios; não varia o ta-
						manho da janela temporal; avalia apenas quatro horários do
						dia.
	Monteiro	et	al.	Cenários analíticos	Grau dos vértices, distância média, coeficiente de	Região urbana/rodovias; Variac ¸ão de densidade; Raio de
	(2013) [15]				agrupamento e conectividade	comunicac ¸ão fixo; Não utiliza grafos temporais e aleatórios;
						área geográfica delimitada; durac ¸ão limitada.
	Cunha et al. (2013-	São Francisco e Zuri-	Grau dos vértices, distância média, coeficiente de	Raio de comunicac ¸ão fixo; compara com grafos aleatórios;
	2014) [5, 4]			que	agrupamento, densidade e persistência de arestas	não varia tamanho da janela temporal.

Par âmetros do modelo Working Day Movement Model.

  

	Parâmetro	Valores
	Pessoas	2 mil
	Grupos	8 grupos em 4 distritos
	Carro próprio	50%
	Locais	Casa, trabalho e áreas de lazer
	Meios de transporte	Ônibus, carro ou táxis
	Simulador	The ONE
	Filtro utilizado	Apenas veículos
	Tabela 2.	

Figura 10. Sobreposic ¸ão to- pol ógica ao longo do dia.

  a) e (b), nota-se que os grafos temporais em Roma apresentaram valores menores que os grafos aleatórios, enquanto que em Helsinque os resultados maiores, indicando que os veículos pessoais repetem mais encontros nos mesmos horários ao longo dos dias, o que não ocorre com táxis. Esses são veículos que retratam o interesse de várias pessoas no mesmo veículo.Assim, a Tabela 4 indica que a base de Helsinque pode ser classificada como uma rede de amigos, pois ela apresenta características sociais com rotinas semelhantes tanto na sobreposic ¸ão topológica e quanto na persistência de arestas. Por outro lado, o cenário de Roma pode ser classificado como uma rede de conhecidos, uma vez que os resultados dos grafos temporais não resultaram valores melhores que os grafos aleatórios na avaliac ¸ão da persistência de arestas.

			Real Aleatório				Real Aleatório				Real Aleatório				Real Aleatório	
	0% 20% 40% 60% Sobreposição topológica				0% 20% 40% 60% Sobreposição topológica					0% 20% 40% 60% 80% Persistência de arestas					0% 20% 40% 60% 80% Persistência de arestas					
	0	6	12 Hora do dia	18	24	0	6	12 Hora do dia	18	24	0	6	12 Hora do dia	18	24	0	6	12 Hora do dia	18	24
	(a) Helsinque			(b) Roma			(a) Helsinque			(b) Roma		

Figura 11. Repetic ¸ão de encontros ao longo do dia.

  

	Base de dados Sobreposic ¸ão Topológica Persistência de Arestas	Classe
	Helsinque	Social	Social	Amigos
	Roma	Social	Aleatório	Conhecidos
	Tabela 4.			

Classificac ¸ão das interac ¸ões social/aleat ório baseado na classificac ¸ão proposta em [24].