Descubrir comunidades en una red, conocido como detección / descubrimiento de comunidades, es un problema fundamental en la ciencia de redes , que atrajo mucha atención en las últimas décadas. En los últimos años, con los tremendos estudios sobre big data , otro problema relacionado pero diferente, llamado búsqueda de comunidad , que tiene como objetivo encontrar la comunidad más probable que contenga el nodo de consulta, ha atraído gran atención tanto del área académica como de la industria. Es una variante dependiente de la consulta del problema de detección de la comunidad. Se puede encontrar una encuesta detallada de la búsqueda comunitaria en la ref., [1] que revisa todos los estudios recientes [2] [3] [4] [5] [6] [7] [8][9] [10] [11]
Como señala el primer trabajo sobre búsqueda de comunidades [2] publicado en SIGKDD'2010, muchos métodos de detección / descubrimiento de comunidades existentes consideran el problema de detección de comunidades estáticas , donde el gráfico debe dividirse a priori sin referencia a los nodos de consulta. Mientras que la búsqueda de comunidad a menudo se enfoca en la comunidad más probable que contenga el vértice de la consulta. Las principales ventajas de la búsqueda de comunidades sobre la detección / descubrimiento de comunidades se enumeran a continuación:
Por ejemplo, un trabajo reciente [9] que se centra en gráficos atribuidos, donde los nodos a menudo se asocian con algunos atributos como palabras clave, e intenta encontrar las comunidades, llamadas comunidades atribuidas, que exhiben una estructura fuerte y cohesión de palabras clave. Los usuarios de la consulta pueden especificar un nodo de consulta y algunas otras condiciones de consulta: (1) un valor, k, el grado mínimo para las comunidades esperadas; y (2) un conjunto de palabras clave, que controlan la semántica de las comunidades esperadas. Las comunidades devueltas se pueden interpretar fácilmente mediante las palabras clave compartidas por todos los miembros de la comunidad. Se pueden encontrar más detalles en. [11]
Algunos estudios recientes [4] [9] han demostrado que, para gráficos de escala de un millón, la búsqueda de comunidades a menudo toma menos de 1 segundo para encontrar una comunidad bien definida, que generalmente es mucho más rápida que muchos métodos de detección / descubrimiento de comunidades existentes. Esto también implica que la búsqueda de comunidades es más adecuada para encontrar comunidades a partir de gráficos grandes.
La búsqueda de comunidades a menudo utiliza algunas métricas de gráficos fundamentales bien definidas para formular la cohesión de las comunidades. Las métricas más utilizadas son k-core (grado mínimo), [2] [4] [6] [7] [9] k-truss, [5] [8] k-edge-connected, [12] [13] Entre estas medidas, la métrica k-core es la más popular y se ha utilizado en muchos estudios recientes, tal como se examinó en. [1]