Estudio comparativo entre el algoritmo de Kleinberg y el algoritmo Biased Selection para la construcción de redes small world
DOI:
https://doi.org/10.13053/cys-21-2-2722Palabras clave:
Biased Selection, cadenas de Markov, grafos, Kleinberg, paseos aleatorios, small world.Resumen
Actualmente las redes de tipo small world constituyen un tema muy importante en nuestro entorno, pues están presentes en varios fenómenos naturales y artificiales. Un objetivo de muchos algoritmos desarrollados para tratamiento de grafos es conseguir que un nodo cualquiera logre establecer una conexión directa con otro nodo del grafo seleccionado al azar obteniendo un “vecino lejano”. Este trabajo muestra un estudio comparativo entre dos algoritmos que logran este objetivo: Kleinberg y Biased Selection. Se demuestra por medio de experimentos que los dos algoritmos son capaces de obtener la distribución de Kleinberg. Se concluye que el algoritmo de Kleinberg obtiene una distribución de muestreo que es directamente proporcional a la distancia Euclidiana, y Biased Selection, a pesar de que también obtiene una distribución directamente proporcional a la distancia Euclidiana, permite que un nodo lejano pueda ser determinado como vecino lejano con mayor frecuencia.Descargas
Publicado
Número
Sección
Licencia
Transfiero exclusivamente a la revista “Computación y Sistemas”, editada por el Centro de Investigación en Computación (CIC), los Derechos de Autor del artículo antes mencionado, asimismo acepto que no serán transferidos a ninguna otra publicación, en cualquier formato, idioma, medio existente (incluyendo los electrónicos y multimedios) o por desarrollar.
Certifico que el artículo, no ha sido divulgado previamente o sometido simultáneamente a otra publicación y que no contiene materiales cuya publicación violaría los Derechos de Autor u otros derechos de propiedad de cualquier persona, empresa o institución. Certifico además que tengo autorización de la institución o empresa donde trabajo o estudio para publicar este Trabajo.
El autor, representante acepta la responsabilidad por la publicación del Trabajo en nombre de todos y cada uno de los autores.
Esta Transferencia está sujeta a las siguientes reservas:
- Los autores conservan todos los derechos de propiedad (tales como derechos de patente) de este Trabajo, con excepción de los derechos de publicación transferidos al CIC, mediante este documento.
- Los autores conservan el derecho de publicar el Trabajo total o parcialmente en cualquier libro del que ellos sean autores o editores y hacer uso personal de este trabajo en conferencias, cursos, páginas web personal, etc.
