[1]ZHAO Danfeng,KONG Wanzai,HUANG Dongmei,et al.Community search schemata and their classification systems based on attribute graphs[J].CAAI Transactions on Intelligent Systems,2024,19(4):791-806.[doi:10.11992/tis.202306050]
Copy

Community search schemata and their classification systems based on attribute graphs

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 19 Number of periods: 2024 4 Page number: 791-806 Column: 综述 Public date: 2024-07-05
Title:
Community search schemata and their classification systems based on attribute graphs
Author(s):
ZHAO Danfeng1;  KONG Wanzai1;  HUANG Dongmei2;  LIU Guohua3
1. School of Information, Shanghai Ocean University, Shanghai 201306, China;
2. Shanghai University of Electric Power, Shanghai 200090, China;
3. School of Computer Science and Technology, Donghua University, Shanghai 201620, China
Keywords:
graph theory; attributed graph; community search; schema; cohesiveness; topology; relation; community search algorithm
CLC:
TP311
DOI:
10.11992/tis.202306050
Abstract:
At present, there are many community search methods in the attribute graph, and there is no systematic classification method, which restricts the application of community search. In order to clarify the category of community search in attribute graph, the classification method of attribute community search is studied. Firstly, the concept of attribute community search schema is proposed to analyze the relationship between attribute community search schemata in depth, proposing four relationships of community search mode of attribute graph: equivalence, affiliation, intersected and exclusion. Secondly, a two-layer classification system is constructed based on the input graph attributes of the search mode, the topology of the output graph and the practical significance of the search mode of each attribute community. The first layer is a family of sets composed of the same set of schemata in the input attribute graph. The input attribute graph here includes sequence, space, keyword, weight, and empty attribute graph. The second layer is each specific community search schema located by the topology and practical meaning of the output graph. Then, the comparative analysis result of corresponding community search algorithm is given for each schema in the second layer. Finally, the characteristics of all the community search modes of attribute graphs are analyzed centrally. Overall, the attribute graph community search pattern not only provides a powerful tool for understanding and analyzing complex network structures, but also provides a new perspective and method for solving practical problems.
References:
[1] LI Xiaoli, WU Min, KWOH Chee-keong, et al. Computational approaches for detecting protein complexes from protein interaction networks: a survey[J]. BMC geno-mics., 2010, 11(1): 1–19.
[2] LI Jiaxin, WANG Xinjue, DENG Ke, et al. Most influential community search over large social networks[C]//2017 IEEE 33rd International Conference on Data Engineering. San Diego: IEEE, 2017: 871-882.
[3] CAI Liwei, WANG Yang. KBGAN: adversarial learning for knowledge graph embeddings[C]//Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. New Orleans: NAACL, 2018: 1470-1480.
[4] SOZIO Mauro, GIONIS Aristides. The community search problem and how to plan a successful cocktail party[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data mining. Washington DC: KDD, 2010: 939-948.
[5] FANG Yixiang, HUANG Xin, QIN Lin, et al. A survey of community search over big graphs[J]. The VLDB journal, 2020, 29(1): 353–392.
[6] BARBIERI N, BONCHI F, GALIMBERTI E, et al. Efficient and effective community search[J]. Data mining and knowledge discovery, 2015, 29(5): 1406–1433.
[7] CUI Wanyun, XIAO Yanghua, Wang Haixun, et al. Local search of communities in large graphs[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. Snowbird: MOD, 2014: 991-1002.
[8] ZHU Junchao, WANG Chaokun. Approaches to community search under complex conditions[J]. Journal of software, 2019, 30(3): 552–572.
[9] FANG Yixiang, WANG Zhihong, CHENG Reynold, et al. Effective and efficient community search over large directed graphs[J]. IEEE transactions on knowledge and data engineering, 2019, 31(11): 2093–2107.
[10] LIU Qing, ZHAO Minjun, HUANG Xin, et al. Truss-based community search over large directed graphs[C]// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York: MOD, 2020: 2183-2197.
[11] LI Zhenjun, LU Yunting, ZHANG Weipeng, et al. Discovering hierarchical subgraphs of k-core-truss[J]. Data science and engineering, 2018, 3(2): 136–149.
[12] HUANF Xin, CHENG Hong, QIN Lin, et al. Querying k-truss community in large and dynamic graphs[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. Snowbird: SIGMOD, 2014: 1311-1322.
[13] AKBAS Esra, ZHAO Peixiang. Truss-based community search: a truss-equivalence based indexing approach[J]. Proceedings of the VLDB endowment, 2017, 10(11): 1298–1309.
[14] HUANG Xin, LAKSHMANAN L V S, YU J X, et al. . Approximate closest community search in networks[EB/OL]. (2015-03-22)[2023-03-25]. https://arxiv.org/abs/1505.05956.pdf.
[15] YUAN Long, QIN Lu, LIN Xuemin, et al. Diversified top-k clique search[J]. The VLDB journal, 2016, 25(2): 171–196.
[16] WU Jun, LI Chumin, JIANG Lu, et al. Local search for diversified Top-k clique search problem[J]. Computers & operations research, 2020, 116: 104867.
[17] PALLA G, DERéNYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814–818.
[18] YUAN Long, QIN Lu, ZHANG Wenjie, et al. Index-based densest clique percolation community search in networks[J]. IEEE transactions on knowledge and data engineering, 2017, 30(5): 922–935.
[19] HU Jiafeng, WU Xiaowei, CHENG R, et al. On minimal steiner maximum-connected subgraph queries[J]. IEEE transactions on knowledge and data engineering, 2017, 29(11): 2455–2469.
[20] CHANG Lijun, LIN Xuemin, QIN Lu, et al. Index-based optimal algorithms for computing steiner components with maximum connectivity[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. Melbourne: MOD, 2015: 459-474.
[21] LI Ronghua, SU Jiao, QIN Lu, et al. Persistent community search in temporal networks[C]//2018 IEEE 34th International Conference on Data Engineering. Paris: IEEE, 2018: 797-808.
[22] RUCHANSKY N, BONCHI F, GARCíA-SORIANO D, et al. To be connected, or not to be connected: that is the minimum inefficiency subgraph problem[C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. New York: CIKM, 2017: 879-888.
[23] TSALOUCHIDOU I, BONCHI F, BAEZA-YATES R. Adaptive community search in dynamic networks[C]//2020 IEEE International Conference on Big Data. Atlanta: IEEE, 2020: 987-995.
[24] GUO Tao, CAO Xin, CONG Gao. Efficient algorithms for answering the m-closest keywords query[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. New York: MOD, 2015: 405-418.
[25] WANG Kai, CAO Xin, LIN Xuemin, et al. Efficient computing of radius-bounded k-cores[C]//2018 IEEE 34th International Conference on Data Engineering. Paris: IEEE, 2018: 233-244.
[26] ZHU Qijun, HU Haibo, XU Cheng, et al. Geo-social group queries with minimum acquaintance constraints[J]. The VLDB journal, 2017, 26(5): 709–727.
[27] CHEN Lu, LIU Chengfei, ZHOU Rui, et al. Maximum co-located community search in large scale social networks[J]. Proceedings of the VLDB endowment, 2018, 11(10): 1233–1246.
[28] LUO Jiehuan, CAO Xin, XIE Xike, et al. Best Co-located community search in attributed networks[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management. New York: CIKM, 2019: 2453-2456.
[29] LUO Jiehuan, CAO Xin, QU Qiang, et al. Efficient search of the most cohesive Co-located community in attributed networks[C]//International Conference on Database Systems for Advanced Applications. Chiang Mai: Springer, 2019: 398-415.
[30] FANG Yixiang, CHENG R, LUO Siqiang, et al. Effective community search for large attributed graphs[J]. Proceedings of the VLDB endowment, 2016, 9(12): 1233–1244.
[31] HUANG Xin, LAKSHMANAN L V S. Attribute-driven community search[J]. Proceedings of the VLDB endowment, 2017, 10(9): 949–960.
[32] GHANBARPOUR A, NIKNAFS K, NADERI H. Efficient keyword search over graph-structured data based on minimal covered r-cliques[J]. Frontiers of information technology & electronic engineering, 2020, 21(3): 448–464.
[33] CHOWDHARY A A, LIU Chengfei, CHEN Lu, et al. Finding attribute diversified communities in complex networks[C]//International Conference on Database Systems for Advanced Applications. Jeju: Springer, 2020: 19-35.
[34] WANG Chunnan, WANG Hongzhi, CHEN Hanxiao, et al. Attributed community search based on effective scoring function and elastic greedy method[J]. Information sciences, 2021, 562: 78–93.
[35] LIU Qing, ZHU Yifan, ZHAO Minjun, et al. VAC: vertex-centric attributed community search[C]//2020 IEEE 36th International Conference on Data Engineering. Dallas: IEEE, 2020.
[36] LI Ronghua, QIN Lu, YU Jeffreyxu, et al. Influential community search in large networks[J]. Proceedings of the VLDB endowment, 2015, 8(5): 509–520.
[37] LI Ronghua, QIN Lu, YE Fanghua, et al. Skyline community search in multi-valued networks[C]//Proceedings of the 2018 International Conference on Management of Data. Houston: MOD, 2018: 457-472.
[38] LUO Wensheng, ZHOU Xu, YANG Jianye, et al. Efficient approaches to Top-R influential community search[J]. IEEE internet of things journal, 2020, 8(16): 12650–12657.
[39] BI Fei, CHANG Lijun, LIN Xuemin, et al. An optimal and progressive approach to online search of top-k influential communities[J]. Proceedings of the VLDB endowment, 2018, 11(9): 1056–1068.
[40] CHEN Shu, WEI Ran, POPOVA D, et al. Efficient computation of importancebased communities in web-scale networks using a single machine[C]//ACM International. Indianapolis: ACM, 2016.
[41] ZHENG Zibin, YE Fanghua, LI Ronghua, et al. Finding weighted K-truss communities in large networks[J]. Information sciences, 2017, 417: 344–360.
[42] XU Jiao, FU Xiaoyi, WU Yiming, et al. Personalized top-n influential community search over large social networks[J]. World wide web, 2020, 23(3): 2153–2184.
[43] XIE Xiaoqin, SONG Mingjie, LIU Chiming, et al. Effective influential community search on attributed graph[J]. Neurocomputing, 2021, 444: 111–125.
[44] SUN Longxu, HUANG Xin, LI Ronghua, et al. Fast algorithms for intimate-core group search in weighted graphs[C]//International Conference on Web Information Systems Engineering. Hong Kong: Springer, 2020: 728-744.
[45] LIU Boge, YUAN Long, LIN Xuemin, et al. Efficient (α, β)-core computation: an index-based approach[C]//The World Wide Web Conference. San Francisco: ACM, 2019: 1130-1141.
[46] WANG Kai, LIN Xuemin, QIN Lu, et al. Efficient bitruss decomposition for large-scale bipartite graphs[C]//2020 IEEE 36th International Conference on Data Engineering. Dallas: IEEE, 2020: 661-672.
[47] ZHANG Yun, PHILLIPS C A, ROGERS G L, et al. On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types[J]. BMC bioinformatics, 2014, 15(1): 1–18.
[48] ZHANG Wenqiang, ZHONG Yingli, YANG Yan. Community search in spatial uncertain network[J]. Journal of physics conference series, 2021, 1952(4): 042112.
[49] LUO Wensheng, ZHOU Xu, LI Kenli, et al. Efficient influential community search in large uncertain graphs[J]. IEEE transactions on knowledge and data engineering, 2021, 35(4): 3779–3793.
[50] MIAO Xiaoye, LIU Yue, GAO Yunjun, et al. Reliable community search on uncertain graphs[C]//2022 IEEE 38th International Conference on Data Engineering. Kuala Lumpur: IEEE, 2022.
[51] 王旭东,韩晓磊,邹功鑫,等. 基于权值的新能源集控电量均衡CSMA/CA改进算法[J]. 微型电脑应用, 2024, 40(5): 227–230
WANG Xudong, HAN Xiaolei, ZOU Gongxin, et al. Improved CSMA/CA algorithm of new energy centralized control power balance based on weight[J]. Microcomputer applications, 2024, 40(5): 227–230
[52] 梁正平,刘程,王志强,等. 基于存档和权值扩展的大规模多目标优化算法[J]. 计算机学报, 2022, 45(5): 951–972
LIANG Zhengping, LIU Cheng, WANG Zhiqiang, et al. Large-scale multi-objective optimization algorithm based on archive and weight extension[J]. Chinese journal of computers, 2022, 45(5): 951–972
[53] 毛华, 刘祎超. 基于权值最大圈的概念格构造算法[J]. 智能系统学报, 2016, 11(4): 519–525
MAO Hua, LIU Yichao. An algorithm for concept lattice construction based on maximum cycles of weight values[J]. CAAI transactions on intelligent systems, 2016, 11(4): 519–525
[54] 陈侃松,李豪科,阮玉龙,等. 基于局部邻居节点和链路权值的改进AODV路由协议[J]. 软件学报, 2021, 32(4): 1186–1200
CHEN Kansong, LI Haoke, RUAN Yulong, et al. Improved AODV routing protocol based on local neighbor nodes and link weights[J]. Journal of software, 2021, 32(4): 1186–1200
[55] 王余蓝. 基于图形数据库的DBLP数据存储[J]. 计算机技术与发展, 2013, 23(8): 18–20, 26
WANG Yulan. DBLP data storage based on graphics database[J]. Computer technology and development, 2013, 23(8): 18–20, 26
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems