커뮤니티 검색

Community search

커뮤니티 검출/검출로 알려진 네트워크 내의 커뮤니티 검출은 네트워크 과학의 근본적인 문제입니다.이 문제는 지난 수십 년 동안 많은 관심을 끌었습니다.최근 빅데이터에 대한 엄청난 연구로 커뮤니티 검색이라는 또 다른 문제, 즉 쿼리 노드를 포함하는 가장 가능성이 높은 커뮤니티를 찾는 것이 목적입니다.이 문제는 학계와 산업 분야 모두에서 큰 관심을 끌고 있습니다.이것은 커뮤니티 검출 문제의 쿼리에 의존하는 변형입니다.커뮤니티 검색에 대한 자세한 조사는 최근의 모든 연구를 검토하는 참조에서 찾을 수 있다.[1]

주요 장점

SIGKDD'2010에서 발표된 커뮤니티[2] 검색에 관한 첫 번째 연구에서 지적되었듯이, 많은 기존 커뮤니티 검출/검출 방법은 쿼리 노드를 참조하지 않고 그래프를 a-priori로 분할해야 하는 정적 커뮤니티 검출 문제를 고려한다.커뮤니티 검색은 종종 쿼리 정점을 포함하는 가장 가능성이 높은 커뮤니티에 초점을 맞춥니다.커뮤니티 검색과 커뮤니티 검출/검출의 주요 장점은 다음과 같습니다.

(1) 고도의 퍼스낼라이제이션.[3][9][10]커뮤니티 검출/검출에서는 많은 경우 동일한 글로벌 기준을 사용하여 서브그래프가 커뮤니티로서 적격인지 여부를 판단합니다.즉, 기준은 정해져 있고, 미리 정해져 있다.그러나 실제로는, 다른 정점에 대한 공동체는 매우 다른 특성을 가질 수 있습니다.또한 커뮤니티 검색을 통해 쿼리 사용자는 보다 개인화된 쿼리 조건을 지정할 수 있습니다.또한 개인화된 쿼리 조건을 통해 커뮤니티를 쉽게 해석할 수 있습니다.

예를 들어, 노드가 키워드 등의 일부 속성과 종종 관련지어져 강력한 구조와 키워드 응집력을 보이는 속성 커뮤니티라고 불리는 커뮤니티를 찾는 최근의 [9]작업입니다.쿼리 사용자는 쿼리 노드 및 기타 쿼리 조건을 지정할 수 있습니다. (1) 값, k, 예상되는 커뮤니티의 최소 정도, (2) 예상되는 커뮤니티의 의미를 제어하는 키워드 세트입니다.반환된 커뮤니티는 커뮤니티 구성원 모두가 공유하는 키워드로 쉽게 해석할 수 있습니다.더 자세한 정보는 [11]에서 얻을 수 있다. 

(2) 고효율.최근 몇 년간 소셜 네트워크의 놀라운 호황과 함께, 정말 큰 그래프들이 많이 있다.예를 들어, 페이스북과 트위터의 사용자 수는 종종 수십억에 이른다.커뮤니티 검출/검출은 소셜 네트워크 전체에서 모든 커뮤니티를 찾는 경우가 많기 때문에 비용이 많이 들고 시간도 많이 소요될 수 있습니다.이와는 대조적으로 커뮤니티 검색은 종종 하위 그래프에서 작동하므로 훨씬 효율적입니다.또한 전체 소셜 네트워크에서 모든 커뮤니티를 탐지하는 것은 종종 불필요합니다.추천이나 소셜 미디어 마켓과 같은 실제 애플리케이션의 경우, 사람들은 종종 모든 커뮤니티보다는 자신이 정말로 관심을 갖고 있는 커뮤니티에 초점을 맞춥니다.

일부 최근[4][9] 연구에 따르면 백만 규모 그래프의 경우 커뮤니티 검색이 잘 정의된 커뮤니티를 찾는 데 1초 미만이 걸리는 경우가 많다. 이는 일반적으로 기존의 많은 커뮤니티 탐지/검출 방법보다 훨씬 빠른 속도이다.이는 또한 커뮤니티 검색이 큰 그래프에서 커뮤니티를 찾는 데 더 적합하다는 것을 의미한다. 

(3) 동적으로 진화하는 [3]그래프를 지원합니다.실제의 거의 모든 그래프는 시간이 지남에 따라 진화하는 경우가 많습니다.커뮤니티 검출은 커뮤니티를 찾기 위해 동일한 글로벌 기준을 사용하는 경우가 많기 때문에 그래프 내의 노드 및 엣지 업데이트에 민감하지 않습니다.즉, 검출된 커뮤니티는 단시간 경과 후 신선도가 저하될 수 있습니다.반대로 커뮤니티 검색은 쿼리 요청에 따라 온라인 방식으로 커뮤니티를 검색할 수 있기 때문에 쉽게 처리할 수 있습니다.

커뮤니티 검색 메트릭

커뮤니티 검색에서는 커뮤니티의 응집력을 나타내기 위해 잘 정의된 기본 그래프 메트릭을 사용하는 경우가 많습니다.일반적으로 사용되는 메트릭은 k-core(최소도),[2][4][6][7][9] k-truss,[5][8] k-edge-connected [12][13]등입니다.이러한 측정법 중에서 k-코어 측정법이 가장 인기 있으며,[1] 에서 조사한 바와 같이 최근 많은 연구에서 사용되고 있다.

레퍼런스

  1. ^ a b Fang, Yixiang; Huang, Xin; Qin, Lu; Zhang, Ying; Zhang, Wenjie; Cheng, Reynold; Lin, Xuemin (2019). "A Survey of Community Search over Big Graphs". arXiv:1904.12539 [cs.DB].
  2. ^ a b c Sozio, Mauro; Gionis, Aristides (2010). "The community-search problem and how to plan a successful cocktail party". Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '10. p. 939. doi:10.1145/1835804.1835923. ISBN 9781450300551. S2CID 11484255.
  3. ^ a b c Cui, Wanyun; Xiao, Yanghua; Wang, Haixun; Lu, Yiqi; Wang, Wei (2013). "Online search of overlapping communities". Proceedings of the 2013 international conference on Management of data - SIGMOD '13. p. 277. doi:10.1145/2463676.2463722. ISBN 9781450320375. S2CID 953025.
  4. ^ a b c Cui, Wanyun; Xiao, Yanghua; Wang, Haixun; Wang, Wei (2014). "Local search of communities in large graphs". Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. pp. 991–1002. doi:10.1145/2588555.2612179. ISBN 9781450323765. S2CID 4653380.
  5. ^ a b Huang, Xin; Cheng, Hong; Qin, Lu; Tian, Wentao; Yu, Jeffrey Xu (2014). "Querying k-truss community in large and dynamic graphs". Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. pp. 1311–1322. doi:10.1145/2588555.2610495. ISBN 9781450323765. S2CID 207211829.
  6. ^ a b Li, Rong-Hua; Qin, Lu; Yu, Jeffrey Xu; Mao, Rui (2015). "Influential community search in large networks". Proceedings of the VLDB Endowment. 8 (5): 509–520. doi:10.14778/2735479.2735484.
  7. ^ a b Barbieri, Nicola; Bonchi, Francesco; Galimberti, Edoardo; Gullo, Francesco (2015). "Efficient and effective community search". Data Mining and Knowledge Discovery. 29 (5): 1406–1433. doi:10.1007/s10618-015-0422-1. S2CID 13440433.
  8. ^ a b Huang, Xin; Lakshmanan, Laks V. S.; Yu, Jeffrey Xu; Cheng, Hong (2015). "Approximate closest community search in networks". Proceedings of the VLDB Endowment. 9 (4): 276–287. arXiv:1505.05956. doi:10.14778/2856318.2856323. S2CID 2905457.
  9. ^ a b c d e Fang, Yixiang; Cheng, Reynold; Luo, Siqiang; Hu, Jiafeng (2016). "Effective community search for large attributed graphs". Proceedings of the VLDB Endowment. 9 (12): 1233–1244. doi:10.14778/2994509.2994538. hdl:10722/232839.
  10. ^ a b Fang, Yixiang; Cheng, Reynold; Li, Xiaodong; Luo, Siqiang; Hu, Jiafeng (2017). "Effective community search over large spatial graphs". Proceedings of the VLDB Endowment. 10 (6): 709–720. doi:10.14778/3055330.3055337. hdl:10722/243528.
  11. ^ a b "Effective Community Search for Large Attributed Graphs".
  12. ^ Chang, Lijun; Lin, Xuemin; Qin, Lu; Yu, Jeffrey Xu; Zhang, Wenjie (2015). "Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity". Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. pp. 459–474. doi:10.1145/2723372.2746486. ISBN 9781450327589. S2CID 18282516.
  13. ^ Hu, Jiafeng; Wu, Xiaowei; Cheng, Reynold; Luo, Siqiang; Fang, Yixiang (2017). "On Minimal Steiner Maximum-Connected Subgraph Queries". IEEE Transactions on Knowledge and Data Engineering. 29 (11): 2455–2469. doi:10.1109/TKDE.2017.2730873. S2CID 40432915.