Agrupamiento local en grafos dirigidos
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
2009
|
| Subjects: | |
| Online Access: | http://eprints.uanl.mx/2091/1/AGRUPAMIENTOLOCAL.pdf |
| _version_ | 1824368145800888320 |
|---|---|
| author | Avalos Gaytán, Vanesa Rivera Ramírez, Mario Schaeffer, Satu Elisa |
| author_facet | Avalos Gaytán, Vanesa Rivera Ramírez, Mario Schaeffer, Satu Elisa |
| author_sort | Avalos Gaytán, Vanesa |
| collection | Repositorio Institucional |
| description | 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. |
| format | Article |
| id | eprints-2091 |
| institution | UANL |
| language | English |
| publishDate | 2009 |
| record_format | eprints |
| spelling | eprints-20912020-02-04T21:18:15Z http://eprints.uanl.mx/2091/ Agrupamiento local en grafos dirigidos Avalos Gaytán, Vanesa Rivera Ramírez, Mario Schaeffer, Satu Elisa QA Matemáticas, Ciencias computacionales 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. 2009 Article PeerReviewed application/pdf en http://eprints.uanl.mx/2091/1/AGRUPAMIENTOLOCAL.pdf http://eprints.uanl.mx/2091/1.haspreviewThumbnailVersion/AGRUPAMIENTOLOCAL.pdf Avalos Gaytán, Vanesa y Rivera Ramírez, Mario y Schaeffer, Satu Elisa (2009) Agrupamiento local en grafos dirigidos. Ciencia UANL, 12 (3). ISSN 1405-9177 |
| spellingShingle | QA Matemáticas, Ciencias computacionales Avalos Gaytán, Vanesa Rivera Ramírez, Mario Schaeffer, Satu Elisa Agrupamiento local en grafos dirigidos |
| thumbnail | https://rediab.uanl.mx/themes/sandal5/images/online.png |
| title | Agrupamiento local en grafos dirigidos |
| title_full | Agrupamiento local en grafos dirigidos |
| title_fullStr | Agrupamiento local en grafos dirigidos |
| title_full_unstemmed | Agrupamiento local en grafos dirigidos |
| title_short | Agrupamiento local en grafos dirigidos |
| title_sort | agrupamiento local en grafos dirigidos |
| topic | QA Matemáticas, Ciencias computacionales |
| url | http://eprints.uanl.mx/2091/1/AGRUPAMIENTOLOCAL.pdf |
| work_keys_str_mv | AT avalosgaytanvanesa agrupamientolocalengrafosdirigidos AT riveraramirezmario agrupamientolocalengrafosdirigidos AT schaeffersatuelisa agrupamientolocalengrafosdirigidos |