[1]赵丹枫,孔万仔,黄冬梅,等.基于属性图的社区搜索模式及其分类体系[J].智能系统学报,2024,19(4):791-806.[doi:10.11992/tis.202306050]
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]
点击复制
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]
基于属性图的社区搜索模式及其分类体系
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
19
期数:
2024年第4期
页码:
791-806
栏目:
综述
出版日期:
2024-07-05
- Title:
- Community search schemata and their classification systems based on attribute graphs
- Keywords:
- graph theory; attributed graph; community search; schema; cohesiveness; topology; relation; community search algorithm
- 分类号:
- TP311
- 摘要:
- 当前在属性图中的社区搜索方法较多、类型繁杂，没有系统的分类方式，约束了社区搜索的应用。为明确属性图社区搜索的类别，对属性图社区搜索分类方法进行研究。首先，首次提出属性图社区搜索模式的概念，深入分析属性图社区搜索模式之间存在的联系，提出属性图社区搜索模式的等价、从属、交叉、全异4种关系；其次，以搜索模式的输入图属性、输出图拓扑结构和各属性图社区搜索模式的实际意义为基础，构建两层分类体系，第1层是由输入属性图相同的模式集合构成的集族，这里的输入属性图包括时序、空间、关键字、权值、空属性图，第2层是由输出图拓扑结构及实际意义定位到的每一个具体的属性图社区搜索模式；然后，针对第2层中每一种模式，给出对应社区搜索算法的对比分析结果；最后，对所有属性图社区搜索模式的特性集中分析。总体而言，属性图社区搜索模式不仅为理解和分析复杂网络结构提供有力工具，也为解决实际问题提供新的视角和方法。
- 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
- 相似文献/References:
-
[1]陈亮,何为,韩力群.RBF神经网络的行车路径代价函数建模[J].智能系统学报,2011,6(5):424.
CHEN Liang,HE Wei,HAN Liqun.Radial basis function neural network modeling of the traffic path cost function[J].CAAI Transactions on Intelligent Systems,2011,6():424.
[2]陈亮,何为,韩力群.城市交通最优路径算法[J].智能系统学报,2012,7(2):167.
CHEN Liang,HE Wei,HAN Liqun.Study on an urban transportation optimal path algorithm[J].CAAI Transactions on Intelligent Systems,2012,7():167.
[3]刘富,姜奕含,邹青宇.复杂网络结构比对算法研究进展[J].智能系统学报,2015,10(4):508.[doi:10.3969/j.issn.1673-4785.201408006]
LIU Fu,JIANG Yihan,ZOU Qingyu.Advances in algorithms for construction alignment of complex networks research[J].CAAI Transactions on Intelligent Systems,2015,10():508.[doi:10.3969/j.issn.1673-4785.201408006]
[4]晁永翠,纪志坚,王耀威,等.复杂网络在路形拓扑结构下可控的充要条件[J].智能系统学报,2015,10(4):577.[doi:10.3969/j.issn.1673-4785.201411031]
CHAO Yongcui,JI Zhijian,WANG Yaowei,et al.Necessary and sufficient conditions for the controllability of complex networks with path topology[J].CAAI Transactions on Intelligent Systems,2015,10():577.[doi:10.3969/j.issn.1673-4785.201411031]
[5]董洁,纪志坚,王晓晓.多智能体网络系统的能控性代数条件[J].智能系统学报,2015,10(5):747.[doi:10.11992/tis.201411030]
DONG Jie,JI Zhijian,WANG Xiaoxiao.Algebraic conditions for the controllability of multi-agent systems[J].CAAI Transactions on Intelligent Systems,2015,10():747.[doi:10.11992/tis.201411030]
[6]王晓晓,纪志坚.广播信号下非一致多智能体系统的能控性[J].智能系统学报,2014,9(4):401.[doi:10.3969/j.issn.1673-4785.201401011]
WANG Xiaoxiao,JI Zhijian.Controllability of non-identical multi-agent systems under a broadcasting control signal[J].CAAI Transactions on Intelligent Systems,2014,9():401.[doi:10.3969/j.issn.1673-4785.201401011]
[7]王康,纪志坚,晁永翠.二阶邻居协议下多智能体系统能控能观性保持[J].智能系统学报,2017,12(2):213.[doi:10.11992/tis.201601022]
WANG Kang,JI Zhijian,CHAO Yongcui.A control strategy for maitaining controllability and observability of a multi-agent system with the second-order neighborhood protocol[J].CAAI Transactions on Intelligent Systems,2017,12():213.[doi:10.11992/tis.201601022]
[8]毛华,史明.利用二元拟阵Kn图的一种建格方法[J].智能系统学报,2017,12(3):333.[doi:10.11992/tis.201704022]
MAO Hua,SHI Ming.A constructive method of lattice using the Kn diagram of binary matroid[J].CAAI Transactions on Intelligent Systems,2017,12():333.[doi:10.11992/tis.201704022]
[9]窦林立,展正然.利用二部图生成概念格[J].智能系统学报,2018,13(5):687.[doi:10.11992/tis.201703026]
DOU Linli,ZHAN Zhengran.Constructing concept lattice using bipartite graph[J].CAAI Transactions on Intelligent Systems,2018,13():687.[doi:10.11992/tis.201703026]
[10]李洁,师五喜,李宝全.多移动机器人固定时间编队控制[J].智能系统学报,2023,18(6):1233.[doi:10.11992/tis.202208021]
LI Jie,SHI Wuxi,LI Baoquan.Fixed-time formation control of multimobile robots[J].CAAI Transactions on Intelligent Systems,2023,18():1233.[doi:10.11992/tis.202208021]
备注/Memo
收稿日期:2023-06-28。
基金项目:国家自然科学青年基金项目（42106190）；国家自然科学基金面上项目（61972241）.
作者简介:赵丹枫，副教授， 博士，主要研究方向为图计算理论、海洋大数据存储、业务流程管理。主持国家自然基金青年科学项目，参与4个国家自然基金面上项目、上海市地方能力建设项目、海洋科技专项等。发表学术论文20余篇。E-mail：dfzhao@shou.edu.cn;孔万仔，硕士研究生，主要研究方向为图计算理论、数据库。E-mail：kwzshou@163.com;刘国华，教授，主要研究方向为数据库理论、隐私保护和BPMS。以主要参加人的身份参与过1项国家自然科学基金项目和多项省自然科学基金项目的研究工作，发表学术论文100余篇，出版专著3部。E-mail：ghliu@dhu.edu.cn
通讯作者:刘国华. E-mail: ghliu@dhu.edu.cn
更新日期/Last Update:
1900-01-01