In this thesis we investigate two topics in data mining on graphs; in the first part we investigate the notion of centrality in graphs, in the second part we look at reconstructing graphs from aggregate information. In many graph related problems the goal is to rank nodes based on an importance score. This score is in general referred to as node centrality. In Part I. we start by giving a novel and more efficient algorithm for computing betweenness centrality. In many applications not an individual node but rather a set of nodes is chosen to perform some task. We generalize the notion of centrality to groups of nodes. While group centrality was first formally defined by Everett and Borgatti (1999), we are the first to pose it as a combinatorial optimization problem; find a group of k nodes with largest centrality. We give an algorithm for solving this optimization problem for a general notion of centrality that subsumes various instantiations of centrality that find paths in the graph. We prove that this problem is NP-hard for specific centrality definitions and we provide a universal algorithm for this problem that can be modified to optimize the specific measures. We also investigate the problem of increasing node centrality by adding or deleting edges in the graph. We conclude this part by solving the optimization problem for two specific applications; one for minimizing redundancy in information propagation networks and one for optimizing the expected number of interceptions of a group in a random navigational network. In the second part of the thesis we investigate what we can infer about a bipartite graph if only some aggregate information -- the number of common neighbors among each pair of nodes -- is given. First, we observe that the given data is equivalent to the dot-product of the adjacency vectors of each node. Based on this knowledge we develop an algorithm that is based on SVD-decomposition, that is capable of almost perfectly reconstructing graphs from such neighborhood data. We investigate two versions of this problem, in the versions the dot-product of nodes with themselves, e.g. the node degrees, are either known or hidden.

Esta pesquisa apresenta uma proposta de reconstrução de matriz OD a partir de dados de velocidade da corrente de tráfego disponíveis na web. Para tal, foram estabelecidos três objetivos específicos, os quais incluem: obtenção e avaliação dos dados de velocidade de tráfego; construção de um modelo computacional e aplicação desse em uma rede real. A avaliação dos dados foi realizada por meio da comparação dos valores de velocidade média da corrente de tráfego obtidos da web com os valores aferidos por sensores do tipo laço indutivo. Os resultados indicam que, apesar das velocidades extraídas da web apresentarem maior variância e valores mais baixos, a maior parcela dos dados obteve diferença similar ou inferior a 11%. Na construção da rotina computacional foi utilizado o Método das Médias Sucessivas (MEMS) e na sua avaliação foram realizados testes comparativos cujas referências foram os resultados alcançados pelo autor do método utilizado. A rotina desenvolvida apresentou melhor resultado com relação ao número total de viagens da matriz reconstruída, além de exigir menor número de iterações. Por outro lado, com relação às viagens atribuídas a cada par OD seu desempenho foi inferior. Para avaliar a aderência a realidade o método proposto foi aplicado a uma rede real composta por trechos específicos das rodovias Presidente Dutra, Pedro I, Ayrton Senna e Governador Carvalho Pinto. Devido ao fato da entrada principal do MEMS ser o volume de veículos, foi necessário estimar o mesmo a partir da velocidade fornecida pela API. A matriz reconstruída apresentou forte dependência da capacidade atribuída às vias, evidenciando a necessidade de definir de forma mais cuidadosa esse parâmetro. Embora, ainda seja necessário aprimorar o método proposto e a rotina computacional elaborada, bem como, aprofundar os estudos da fonte de dados utilizada, o experimento de caráter exploratório mostra a possibilidade de reconstruir uma matriz OD a partir de dados disponíveis na web. / This research presents a proposal for the reconstruction of OD matrix from traffic stream velocity data available on the web. To this end, three specific objectives have been established, which include: obtaining and evaluating traffic speed data; construction of a computational model and application of this in a real network. The data were evaluated by the comparison of the mean values of the traffic current, obtained from the web, with those measured by loop sensors. The results indicate that, although the velocities extracted from the web presented higher variance and lower values, the greater part of the data obtained a difference similar to or lower than 11%. In the construction of the computational routine was used the Method of Successive Averages (MEMS) and in its evaluation were performed comparative tests whose references were the results achieved by the author of the used method. The developed routine presented better results in relation to the total number of trips of the reconstructed OD matrix, besides requiring a smaller number of iterations. On the other hand, in relation to the trips attributed to each OD pair the performance was lower. To evaluate the adherence to reality, the proposed method was applied to a real network composed of specific sections of the Presidente Dutra, Pedro I, Ayrton Senna and Governador Carvalho Pinto highways. Due to the fact that the main input of the MEMS is the vehicles flow, was necessary to estimate it from the speed provided by the API. The reconstructed matrix presented a strong dependence on the capacity attributed to the roads, evidencing the need to define this parameter more carefully. Although it is still necessary to improve the proposed method and the elaborated computational routine, as well as to deepen the studies of the used data source, the exploratory experiment shows the possibility of reconstructing an OD matrix from data available on the web.

Esta pesquisa apresenta uma proposta de reconstrução de matriz OD a partir de dados de velocidade da corrente de tráfego disponíveis na web. Para tal, foram estabelecidos três objetivos específicos, os quais incluem: obtenção e avaliação dos dados de velocidade de tráfego; construção de um modelo computacional e aplicação desse em uma rede real. A avaliação dos dados foi realizada por meio da comparação dos valores de velocidade média da corrente de tráfego obtidos da web com os valores aferidos por sensores do tipo laço indutivo. Os resultados indicam que, apesar das velocidades extraídas da web apresentarem maior variância e valores mais baixos, a maior parcela dos dados obteve diferença similar ou inferior a 11%. Na construção da rotina computacional foi utilizado o Método das Médias Sucessivas (MEMS) e na sua avaliação foram realizados testes comparativos cujas referências foram os resultados alcançados pelo autor do método utilizado. A rotina desenvolvida apresentou melhor resultado com relação ao número total de viagens da matriz reconstruída, além de exigir menor número de iterações. Por outro lado, com relação às viagens atribuídas a cada par OD seu desempenho foi inferior. Para avaliar a aderência a realidade o método proposto foi aplicado a uma rede real composta por trechos específicos das rodovias Presidente Dutra, Pedro I, Ayrton Senna e Governador Carvalho Pinto. Devido ao fato da entrada principal do MEMS ser o volume de veículos, foi necessário estimar o mesmo a partir da velocidade fornecida pela API. A matriz reconstruída apresentou forte dependência da capacidade atribuída às vias, evidenciando a necessidade de definir de forma mais cuidadosa esse parâmetro. Embora, ainda seja necessário aprimorar o método proposto e a rotina computacional elaborada, bem como, aprofundar os estudos da fonte de dados utilizada, o experimento de caráter exploratório mostra a possibilidade de reconstruir uma matriz OD a partir de dados disponíveis na web. / This research presents a proposal for the reconstruction of OD matrix from traffic stream velocity data available on the web. To this end, three specific objectives have been established, which include: obtaining and evaluating traffic speed data; construction of a computational model and application of this in a real network. The data were evaluated by the comparison of the mean values of the traffic current, obtained from the web, with those measured by loop sensors. The results indicate that, although the velocities extracted from the web presented higher variance and lower values, the greater part of the data obtained a difference similar to or lower than 11%. In the construction of the computational routine was used the Method of Successive Averages (MEMS) and in its evaluation were performed comparative tests whose references were the results achieved by the author of the used method. The developed routine presented better results in relation to the total number of trips of the reconstructed OD matrix, besides requiring a smaller number of iterations. On the other hand, in relation to the trips attributed to each OD pair the performance was lower. To evaluate the adherence to reality, the proposed method was applied to a real network composed of specific sections of the Presidente Dutra, Pedro I, Ayrton Senna and Governador Carvalho Pinto highways. Due to the fact that the main input of the MEMS is the vehicles flow, was necessary to estimate it from the speed provided by the API. The reconstructed matrix presented a strong dependence on the capacity attributed to the roads, evidencing the need to define this parameter more carefully. Although it is still necessary to improve the proposed method and the elaborated computational routine, as well as to deepen the studies of the used data source, the exploratory experiment shows the possibility of reconstructing an OD matrix from data available on the web.