Hispanopedia Wiki
Articulo de referencia

Búsqueda en la comunidad

Descubrir 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...

Hispanopedia WikiContenido en espanolLectura gratuita

Descubrir 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 , con los numerosos 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 contiene el nodo de consulta, ha atraído gran atención tanto en el ámbito académico como en el industrial. Es una variante del problema de detección de comunidades que depende de la consulta. Un estudio detallado de la búsqueda de comunidades se puede encontrar en la referencia [ 1 ] que revisa todos los estudios recientes [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]

Ventajas principales

Como se señaló en el primer trabajo sobre búsqueda de comunidades [ 2 ] publicado en SIGKDD'2010, muchos métodos existentes de detección/descubrimiento de comunidades consideran el problema de detección de comunidades estáticas , donde el grafo debe particionarse a priori sin referencia a los nodos de consulta. Mientras que la búsqueda de comunidades a menudo se centra en las comunidades más probables que contienen el vértice de consulta . Las principales ventajas de la búsqueda de comunidades sobre la detección/descubrimiento de comunidades se enumeran a continuación:

Alta personalización

La detección/descubrimiento de comunidades suele utilizar el mismo criterio global para determinar si un subgrafo califica como comunidad. En otras palabras, el criterio es fijo y predeterminado. Sin embargo, en realidad, las comunidades para diferentes vértices pueden tener características muy distintas. Además, la búsqueda de comunidades permite a los usuarios especificar condiciones de consulta más personalizadas. Asimismo, estas condiciones personalizadas facilitan la interpretación de las comunidades. [ 3 ] [ 9 ] [ 10 ]

For example, a recent work,[9] which focuses on attributed graphs, where nodes are often associated with some attributes like keyword, and tries to find the communities, called attributed communities, which exhibit both strong structure and keyword cohesiveness. The query users are allowed to specify a query node and some other query conditions: (1) a value, k, the minimum degree for the expected communities; and (2) a set of keywords, which control the semantic of the expected communities. The communities returned can be easily interpreted by the keywords shared by all the community members. More details can be found from.[11]

High efficiency

With the striking booming of social networks in recent years, there are many real big graphs. For example, the numbers of users in Facebook and Twitter are often billions-scale. As community detection/discovery often finds all the communities from an entire social network, this can be very costly and also time-consuming. In contrast, community search often works on a sub-graph, which is much efficient. Moreover, detecting all the communities from an entire social network is often unnecessary. For real applications like recommendation and social media markets, people often focus on some communities that they are really interested in, rather than all the communities.

Some recent studies[4][9] have shown that, for million-scale graphs, community search often takes less than 1 second to find a well-defined community, which is generally much faster than many existing community detection/discovery methods. This also implies that, community search is more suitable for finding communities from big graphs.

Support for dynamically evolving graphs

Almost all the graphs in real life are often evolving over time. Since community detection often uses the same global criterion to find communities, they are not sensitive of the updates of nodes and edges in graphs.[3] In other words, the detected communities may loose freshness after a short period of time. On the contrary, community search can handle this easily since it is able to search the communities in an online manner, based on a query request.

La búsqueda de comunidades a menudo utiliza algunas métricas de grafos fundamentales y bien definidas para formular la cohesión de las comunidades. Las métricas comúnmente utilizadas son k-core (grado mínimo), [ 2 ] [ 4 ] [ 6 ] [ 7 ] [ 9 ] k-truss (métrica) , [ 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 analiza en. [ 1 ]

Referencias

  1. 1 2 Colmillo, Yixiang; Huang, Xin; Qin, Lu; Zhang, Ying; Zhang, Wenjie; Cheng, Reynold; Lin, Xuemin (2019). "Una encuesta sobre búsqueda comunitaria en grandes gráficos". arXiv : 1904.12539 [ cs.DB ].
  2. 1 2 3 Sozio, Mauro; Gionis, Aristides (2010). "El problema de la búsqueda de comunidades y cómo planificar una fiesta de cóctel exitosa". Actas de la 16.ª conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos - KDD '10 . p. 939. doi : 10.1145/1835804.1835923 . ISBN  9781450300551. S2CID 11484255 . 
  3. 1 2 3 Cui, Wanyun; Xiao, Yanghua; Wang, Haixun; Lu, Yiqi; Wang, Wei (2013). "Búsqueda en línea de comunidades superpuestas". Actas de la conferencia internacional de 2013 sobre Gestión de datos - SIGMOD '13 . pág. 277. doi : 10.1145/2463676.2463722 . ISBN  9781450320375. S2CID 953025 . 
  4. 1 2 3 Cui, Wanyun; Xiao, Yanghua; Wang, Haixun; Wang, Wei (2014). "Búsqueda local de comunidades en grafos grandes". Actas de la Conferencia Internacional ACM SIGMOD 2014 sobre Gestión de Datos . págs. 991–1002 . doi : 10.1145/2588555.2612179 . ISBN  9781450323765. S2CID 4653380 . 
  5. 1 2 Huang, Xin; Cheng, Hong; Qin, Lu; Tian, ​​Wentao; Yu, Jeffrey Xu (2014). "Consulta de la comunidad k-truss en grafos grandes y dinámicos". Actas de la Conferencia Internacional ACM SIGMOD 2014 sobre Gestión de Datos . págs. 1311–1322 . doi : 10.1145/2588555.2610495 . ISBN  9781450323765. S2CID 207211829 . 
  6. 1 2 Li, Rong-Hua; Qin, Lu; Yu, Jeffrey Xu; Mao, Rui (2015). "Búsqueda de comunidades influyentes en grandes redes". Actas del Fondo de Dotación VLDB . 8 (5): 509– 520. CiteSeerX 10.1.1.667.4074 . doi : 10.14778/2735479.2735484 . S2CID 17672355 .  
  7. 1 2 Barbieri, Nicola; Bonchi, Francisco; Galimberti, Edoardo; Gullo, Francesco (2015). "Búsqueda comunitaria eficiente y eficaz". Minería de datos y descubrimiento de conocimientos . 29 (5): 1406– 1433. doi : 10.1007/s10618-015-0422-1 . S2CID 13440433 . 
  8. 1 2 Huang, Xin; Lakshmanan, Laks VS; Yu, Jeffrey Xu; Cheng, Hong (2015). "Búsqueda aproximada de la comunidad más cercana en redes". Actas de la Fundación VLDB . 9 (4): 276– 287. arXiv : 1505.05956 . doi : 10.14778/2856318.2856323 . S2CID 2905457 . 
  9. 1 2 3 4 5 Fang, Yixiang; Cheng, Reynold; Luo, Siqiang; Hu, Jiafeng (2016). "Búsqueda efectiva de comunidades para grafos con atributos grandes". Actas de la Fundación VLDB . 9 (12): 1233– 1244. doi : 10.14778/2994509.2994538 . hdl : 10722/232839 .
  10. 1 2 Fang, Yixiang; Cheng, Reynold; Li, Xiaodong; Luo, Siqiang; Hu, Jiafeng (2017). "Búsqueda efectiva de comunidades en grandes grafos espaciales". Actas de la Fundación VLDB . 10 (6): 709– 720. doi : 10.14778/3055330.3055337 . hdl : 10722/243528 .
  11. 1 2 "Búsqueda efectiva de comunidades para grafos con atributos grandes" .
  12. ↑ Chang, Lijun; Lin, Xuemin; Qin, Lu; Yu, Jeffrey Xu; Zhang, Wenjie (2015). «Algoritmos óptimos basados ​​en índices para el cálculo de componentes Steiner con máxima conectividad». Actas de la Conferencia Internacional ACM SIGMOD de 2015 sobre Gestión de Datos . págs. 459–474 . doi : 10.1145/2723372.2746486 . ISBN  9781450327589. S2CID 18282516 . 
  13. ^ Hu, Jiafeng; Wu, Xiaowei; Cheng, Reynold; Luo, Siqiang; Colmillo, Yixiang (2017). "Sobre consultas de subgrafos mínimos y máximos conectados de Steiner". Transacciones IEEE sobre conocimiento e ingeniería de datos . 29 (11): 2455– 2469. Código bibliográfico : 2017ITKDE..29.2455H . doi : 10.1109/TKDE.2017.2730873 . S2CID 40432915 .