| Popis: |
En este trabajo se presenta un método de agrupamiento local en grafos dirigidos: dado un vértice semilla, se determinó el grupo de vértices al que pertenece de tal forma que los vértices seleccionados sean estructuralmente cercanos de la semilla. A un grafo dirigido se le puede asociar una cadena de Markov que corresponde a una caminata aleatoria ciega en el grafo. Se aprovechó esta conexión para expresar cercanía estructural en términos de los tiempos de absorción para detectar vértices que son “cercanos” al vértice semilla. Se detectó el grupo de un vértice a través de caminatas aleatorias cortas repetidas desde el vértice semilla, analizando la frecuencia de visitas a los otros vértices. Se experimentó con grafos pequeños para comparar el resultado los tiempos exactos de absorción. El agrupamiento local puede ser aplicado a diferentes fenómenos reales, por ejemplo, en propagación de epidemias, balanceo de carga, etc. We propose a method for local clustering in directed graphs: we determine a group of «nearby» vertices to a seed vertex, such that the selected vertices are structurally close to the given vertex. For a directed graph, there is a Markov chain that corresponds to a blind random walk in the graph. We use this connection to express structural closeness in terms of absorption times to detect vertices that are «near» the seed vertex. We detect the cluster of a vertex by repeated short random walks starting at the seed and use the visit frequencies to determine which vertices are nearby. We experiment on small graphs and compare the results with globally computed absorption times. Local clustering can be applied to various real phenomena, such as epidemics propagation, load balancing, etc. |
