Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Searching Target Communities with Outliers in attributed graph

Published: 10 January 2022 Publication History

Abstract

Classical community search methods aim to detect local communities containing a set of sample nodes provided by users, which have been wildly studied in recent years. Existing efforts on community search have mainly detected communities where the sample nodes are located. Nevertheless, they may fail to capture communities without sample nodes but are similar with user’s preference deduced from the given sample nodes. We argue that community search should take user’s preference into account during searching process, steering the algorithm to capture more interesting parts of the entire attributed graph.
In this work, we propose a community search model that is capable of finding multiple target communities with few given sample nodes and simultaneously identify outliers in attributed network. The model is termed as Searching Target Communities with Outliers (STCO), which collaborates user’s preference into the process of searching to find interesting clusters of the entire network. Particularly, we specify two STCO methods, named STCOE and STCOT, based on two strategies of exploring sample node candidates, respectively. The average partition similarity is defined on the expanded candidate node set to infer the attribute subspace as user’s latent interest. And then, multiple communities and outliers in the whole network are detected via fractional-core and structural constraints. We demonstrate the effectiveness and efficiency of our model on several synthetic and real-world attributed networks with different scales and subjects.

References

[1]
Jin Di, You Xinxin, Li Weihao, He Dongxiao, Cui, Incorporating network embedding into markov random field for better community detection, Proceedings of the AAAI Conference on Artificial Intelligence, 2019, pp. 160–167.
[2]
Xiao Huang, Qingquan Song, Yuening Li, Xia Hu, Graph recurrent networks with attributed random walks, in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019, pp. 732–740.
[3]
Phillip A. Rivas, Community based targeted advertising. September 3 2009. US Patent App. 12/039, p. 400.
[4]
Lee Juyong, Lee Jooyoung, Hidden information revealed by optimal community structure from a protein-complex bipartite network improves protein function prediction, PLoS One 8 (4) (2013).
[5]
Mauro Sozio, Aristides Gionis, The community-search problem and how to plan a successful cocktail party, in: Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining, 2010, pp. 939–948.
[6]
Huang Xin, Lakshmanan Laks V.S., Yu Jeffrey Xu, Cheng Hong, Approximate closest community search in networks, 2015, arXiv preprint arXiv:1505.05956.
[7]
Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, Jeffrey Xu Yu, Querying k-truss community in large and dynamic graphs, in: Proceedings of the ACM SIGMOD international conference on Management of data, 2014, pp. 1311–1322.
[8]
Meng Fanrong, Rui Xiaobin, Wang Zhixiao, Xing Yan, Cao Longbing, Coupled node similarity learning for community detection in attributed networks, Entropy 20 (6) (2018) 471.
[9]
Huang Xin, Lakshmanan Laks V.S., Attribute-driven community search, Proc. VLDB Endow. 10 (9) (2017) 949–960.
[10]
Liu Haijiao, Ma Huifang, Chang Yang, Li Zhixin, Wu Wenjuan, Leveraging user preferences for community search via attribute subspace, in: International Conference on Knowledge Science, Engineering and Management, Springer, 2019, pp. 584–595.
[11]
Fang Yixiang, Cheng Reynolds, Luo Siqiang, Hu Jiafeng, Effective community search for large attributed graphs, Proc. VLDB Endow. 9 (12) (2016) 1233–1244.
[12]
Bryan Perozzi, Leman Akoglu, Patricia Iglesias Sánchez, Emmanuel Müller, Focused clustering and outlier detection in large attributed graphs, in: Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining, 2014, pp. 1346–1355.
[13]
Wu Peng, Pan Li, Mining target attribute subspace and set of target communities in large attributed networks, 2017, arXiv preprint arXiv:1705.03590.
[14]
Wanyun Cui, Yanghua Xiao, Haixun Wang, Yiqi Lu, Wei Wang, Online search of overlapping communities, in: Proceedings of the ACM SIGMOD international conference on Management of data, 2013, pp. 277–288.
[15]
Wanyun Cui, Yanghua Xiao, Haixun Wang, Wei Wang, Local search of communities in large graphs, in: Proceedings of the ACM SIGMOD international conference on Management of data, 2014, pp. 991–1002.
[16]
Clauset Aaron, Finding local community structure in networks, Phys. Rev. E 72 (2) (2005).
[17]
Liu Saisai, Xia Zhengyou, A two-stage bfs local community detection algorithm based on node transfer similarity and local clustering coefficient, Physica A 537 (2020).
[18]
Luo Wenjian, Lu Nannan, Ni Li, Zhu Wenjie, Ding Weiping, Local community detection by the nearest nodes with greater centrality, Inform. Sci. 517 (2020) 377–392.
[19]
Zhou Yang, Cheng Hong, Yu Jeffrey Xu, Graph clustering based on structural/attribute similarities, Proc. VLDB Endow. 2 (1) (2009) 718–729.
[20]
Akoglu Leman, Tong Hanghang, Meeder Brendan, Faloutsos Christos, Pics: Parameter-free identification of cohesive subgroups in large attributed graphs, in: Proceedings of the SIAM International Conference on Data Mining, SIAM, 2012, pp. 439–450.
[21]
Shang Jingwen, Wang Chaokun, Wang Changping, Guo Gaoyang, Qian Jun, An attribute-based community search method with graph refining, J. Supercomput. (2017) 1–28.
[22]
Liu Qing, Zhu Yifan, Zhao Minjun, Huang Xin, Xu Jianliang, Gao Yunjun, Vac: Vertex-centric attributed community search, in: IEEE International Conference on Data Engineering, ICDE, IEEE, 2020, pp. 937–948.
[23]
Liu Haijiao, Ma Huifang, Chang Yang, Li Zhixin, Wu Wenjuan, Target community detection with user’s preference and attribute subspace, IEEE Access 7 (2019) 46583–46594.
[24]
Ye Wei, Mautz Dominik, Böhm Christian, Singh Ambuj, Plant Claudia, Plant incorporating user’s preference into attributed graph clustering, IEEE Trans. Knowl. Data Eng. (2020).
[25]
Ye Li, Chaofeng Sha, Xin Huang, Yanchun Zhang, Community detection in attributed graphs: An embedding approach, in: Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
[26]
Mántaras R. López De, A distance-based attribute selection measure for decision tree induction, Mach. Learn. 6 (1) (1991) 81–92.
[27]
Seidman Stephen B., Network structure and minimum degree, Social Networks 5 (3) (1983) 269–287.
[28]
Ebadian Soroush, Huang Xin, Fast algorithm for k-truss discovery on public–private graphs, 2019, arXiv preprint arXiv:1906.00140.
[29]
Wu Jun, Li Chu-Min, Jiang Lu, Zhou Junping, Yin Minghao, Local search for diversified top-k clique search problem, Comput. Oper. Res. 116 (2020).
[30]
Giatsidis Christos, Thilikos Dimitrios M., Vazirgiannis Michalis, Evaluating cooperation in communities with the k-core structure, in: International Conference on Advances in Social Networks Analysis and Mining, IEEE, 2011, pp. 87–93.
[31]
Aydin Kevin, Bateni MohammadHossein, Mirrokni Vahab, Distributed balanced partitioning via linear embedding, Algorithms 12 (8) (2019) 162.

Cited By

View all
  • (2024)Attribute subspace-guided multi-scale community detectionNeural Computing and Applications10.1007/s00521-024-09751-636:22(13975-13988)Online publication date: 1-Aug-2024
  • (2023)Multiresolution Local Spectral Attributed Community SearchACM Transactions on the Web10.1145/362458018:1(1-28)Online publication date: 19-Sep-2023
  • (2023)Polarized Communities Search via Co-guided Random Walk in Attributed Signed NetworksACM Transactions on Internet Technology10.1145/361344923:4(1-22)Online publication date: 17-Nov-2023
  • Show More Cited By

Index Terms

  1. Searching Target Communities with Outliers in attributed graph
    Index terms have been assigned to the content through auto-classification.

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image Knowledge-Based Systems
    Knowledge-Based Systems  Volume 235, Issue C
    Jan 2022
    878 pages

    Publisher

    Elsevier Science Publishers B. V.

    Netherlands

    Publication History

    Published: 10 January 2022

    Author Tags

    1. Community search
    2. Attributed graph
    3. Average partition similarity
    4. Attribute subspace
    5. Outliers

    Qualifiers

    • Research-article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 20 Nov 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Attribute subspace-guided multi-scale community detectionNeural Computing and Applications10.1007/s00521-024-09751-636:22(13975-13988)Online publication date: 1-Aug-2024
    • (2023)Multiresolution Local Spectral Attributed Community SearchACM Transactions on the Web10.1145/362458018:1(1-28)Online publication date: 19-Sep-2023
    • (2023)Polarized Communities Search via Co-guided Random Walk in Attributed Signed NetworksACM Transactions on Internet Technology10.1145/361344923:4(1-22)Online publication date: 17-Nov-2023
    • (2023)Efficient multi-scale community search method based on spectral graph waveletFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-022-2220-417:5Online publication date: 1-Oct-2023
    • (2023)Local Spectral for Polarized Communities Search in Attributed Signed NetworkDatabase Systems for Advanced Applications10.1007/978-3-031-30675-4_5(58-74)Online publication date: 17-Apr-2023

    View Options

    View options

    Login options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media