El descubrimiento de comunidades en una red, conocido como detección/descubrimiento de comunidades, es un problema fundamental en la ciencia de redes , que ha atraído mucha atención en las últimas décadas. En los últimos años [ ¿cuándo? ] , con los tremendos estudios sobre big data , otro problema relacionado pero diferente, llamado búsqueda de comunidades , que tiene como objetivo encontrar la comunidad más probable que contenga el nodo de consulta, ha atraído gran atención tanto de las áreas académicas como de la industria. Es una variante dependiente de la consulta del problema de detección de comunidades. Se puede encontrar un estudio detallado de la búsqueda de comunidades en la referencia [1], que revisa todos los estudios recientes [2] [3] [4] [5 ] [6] [7] [8] [9] [10] [11]
Como se señala en el primer trabajo sobre búsqueda de comunidades [2] publicado en SIGKDD'2010, muchos de los 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. Si bien la búsqueda de comunidades a menudo se centra en las comunidades más probables que contienen el vértice de consulta [ aclaración necesaria ] . Las principales ventajas de la búsqueda de comunidades sobre la detección/descubrimiento de comunidades se enumeran a continuación:
(1) Alta personalización. [3] [9] [10] La detección/descubrimiento de comunidades a menudo utiliza el mismo criterio global para decidir si un subgrafo califica como una comunidad. En otras palabras, el criterio es fijo y predeterminado. Pero en realidad, las comunidades para diferentes vértices pueden tener características muy diferentes. Además, la búsqueda de comunidades permite a los usuarios de la consulta especificar condiciones de consulta más personalizadas. Además, las condiciones de consulta personalizadas permiten que las comunidades se interpreten fácilmente.
Por ejemplo, un trabajo reciente, [9] que se centra en los gráficos atribuidos, donde los nodos suelen estar asociados a 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 por las palabras clave compartidas por todos los miembros de la comunidad. Se pueden encontrar más detalles en [11] .
(2) Alta eficiencia. Con el sorprendente auge de las redes sociales en los últimos años, existen muchos gráficos realmente grandes. Por ejemplo, las cifras de usuarios en Facebook y Twitter suelen ser de miles de millones. Como la detección/descubrimiento de comunidades a menudo encuentra todas las comunidades de una red social completa, esto puede ser muy costoso y también consumir mucho tiempo. En cambio, la búsqueda de comunidades a menudo funciona en un subgráfico, lo que es mucho más eficiente. Además, la detección de todas las comunidades de una red social completa a menudo es innecesaria. Para aplicaciones reales como la recomendación y los mercados de medios sociales , las personas a menudo se centran en algunas comunidades en las que están realmente interesados, en lugar de en todas las comunidades.
Algunos estudios recientes [4] [9] han demostrado que, en el caso de gráficos de escala de millones, la búsqueda de comunidades suele tardar menos de un segundo en encontrar una comunidad bien definida, lo que suele ser mucho más rápido que muchos métodos de detección y descubrimiento de comunidades existentes. Esto también implica que la búsqueda de comunidades es más adecuada para encontrar comunidades en gráficos grandes.
(3) Soporte para gráficos que evolucionan dinámicamente. [3] Casi todos los gráficos en la vida real a menudo evolucionan con el tiempo. Dado que la detección de comunidades a menudo utiliza el mismo criterio global para encontrar comunidades, no son sensibles a las actualizaciones de nodos y aristas en los gráficos. En otras palabras, las comunidades detectadas pueden perder frescura después de un corto período de tiempo. Por el contrario, la búsqueda de comunidades puede manejar esto fácilmente ya que puede buscar las comunidades de manera en línea, en función de una solicitud de consulta.
La búsqueda de comunidades suele utilizar algunas métricas de grafos fundamentales bien definidas para formular la cohesión de las comunidades. Las métricas que se utilizan habitualmente son k-core (grado mínimo), [2] [4] [6] [ 7] [9] k-truss, [5] [8] k-edge-connected, [12] [13] etc. Entre estas medidas, la métrica k-core es la más popular y se ha utilizado en muchos estudios recientes, como se muestra en [1] .