属性网络中结合用户偏好的社区搜索和离群点检测

doi:10.12263/DZXB.20210370

电子学报 ›› 2022, Vol. 50 ›› Issue (9): 2172-2180.DOI: 10.12263/DZXB.20210370

属性网络中结合用户偏好的社区搜索和离群点检测

李青青¹, 马慧芳¹^,²(), 李举¹, 李志欣³, 姜彦斌¹

^1.西北师范大学计算机科学与工程学院, 甘肃兰州 730070
^2.桂林电子科技大学广西可信软件重点实验室, 广西桂林 541004
^3.广西师范大学广西多源信息挖掘与安全重点实验室, 广西桂林 541004

收稿日期:2021-03-18 修回日期:2021-11-13 出版日期:2022-09-25
- 通讯作者:
- 马慧芳
- 作者简介:
- 李青青　女，1995年5月出生于甘肃省庆阳市. 现就读于西北师范大学计算机科学与工程学院. 主要研究方向为社区搜索. E-mail: 2019211784@nwnu.edu.cn
  马慧芳　女， 1984年7月出生于甘肃省兰州市. 2010年毕业于中国科学院计算技术研究所. 现为西北师范大学计算机科学与工程学院教授，主要研究方向为人工智能，数据挖掘与机器学习.
  李举　男， 1995年1月出生于山西省大同市. 现就读于西北师范大学计算机科学与工程学院. 主要研究方向为社区搜索. E-mail: 2019221843@nwnu.edu.cn
  李志欣　1971年10月出生，广西桂林人. 2010年于中国科学院计算技术研究所博士研究生毕业，获工学博士学位. 现为广西师范大学计算机科学与工程学院教授、博士生导师，主要研究方向为图像理解、机器学习、跨媒体计算.E-mail: lizx@gxnu.edu.cn
  姜彦斌　男. 1996年1月出生于甘肃省陇南市. 现就读于西北师范大学计算机科学与工程学院. 主要研究方向为推荐系统，图神经网络. E-mail: jiangyanbin@nwnu.edu.cn
- 基金资助:
- 国家自然科学基金 (61762078); 广西多源信息挖掘与安全重点实验室开放基金 (MIMS18-08); 西北师范大学2019年度青年教师科研能力提升计划重大项目 (NWNU-LKQN2019-2)

Incorporating User Preference for Community Search and Outlier Detection in Attributed Network

LI Qing-qing¹, MA Hui-fang¹^,²(), LI Ju¹, LI Zhi-xin³, JIANG Yan-bin¹

^1.College of Computer Science and Engineering，Northwest Normal University，Lanzhou，Gansu 730070，China
^2.Guangxi Key Laboratory of Trusted Software，Guilin University of Electronic Science and Technology，Guilin，Guangxi 541004，China
^3.Guangxi Key Lab of Multi-Source Information Mining & Security，Guangxi Normal University，Guilin，Guangxi 541004，China

Received:2021-03-18 Revised:2021-11-13 Online:2022-09-25 Published:2022-10-26
- Corresponding author:
- MA Hui-fang

摘要/Abstract

摘要：

社区搜索是备受关注的网络分析任务之一，旨在搜寻包含查询节点的局部社区.现有大多数社区搜索方法多面向简单网络且仅能定位查询节点所在社区，未能在搜索过程中考虑用户偏好.为实现利用用户偏好指导搜索过程并搜寻用户感兴趣的多社区，设计了属性网络中结合用户偏好的社区搜索和离群点检测方法，旨在通过较少的查询节点有效的捕获用户偏好并自动探索网络中的社区，同时识别社区中离群点.具体而言，通过编码查询节点及其邻居间的显式交互关系和相似属性以突出局部结构，利用其来挖掘潜在查询节点候选集成员.在查询节点候选集上定义平均划分相似度以推断属性子空间为用户潜在兴趣.采用属性和结构约束来搜索网络中的多社区和离群点.此外，真实数据集和人工数据集上的大量实验证明了所提方法的有效性.

关键词: 属性网络, 社区搜索, 平均划分相似度, 属性子空间, 离群点

Abstract:

Community search aims to search local communities containing query nodes, which is one of the most concerned studies in network analysis task. Most existing community search methods are oriented to simple network and can only detect the community where query nodes are located. They may fail to take user's preferences into account during searching process. To guide the process of community search via user's preferences for finding multi-communities that users are interested in, we propose a community search method that is capable of searching multi-communities with user's preference and simultaneously identify outliers via few given query nodes in attributed network. Clearly, we explicitly model interactions between query nodes with its neighbors and encode similar attributes to highlight the local structure, which could be beneficial for query nodes to mine potential candidates. And we define the average partition similarity on candidate set of query nodes to infer attribute subspace as user's latent interest. Multi-communities and outliers in the whole network are detected via fractional-core and structural constraints. Experiments on real and synthetic network datasets demonstrate the effectiveness of the proposed algorithm.

Key words: attributed network, community search, average partition similarity, attribute subspace, outliers

中图分类号:

TP181

李青青, 马慧芳, 李举, 李志欣, 姜彦斌. 属性网络中结合用户偏好的社区搜索和离群点检测[J]. 电子学报, 2022, 50(9): 2172-2180.

LI Qing-qing, MA Hui-fang, LI Ju, LI Zhi-xin, JIANG Yan-bin. Incorporating User Preference for Community Search and Outlier Detection in Attributed Network[J]. Acta Electronica Sinica, 2022, 50(9): 2172-2180.

图/表 9

参考文献 25

1	JIN D, YOU X X, LI W H, et al. Incorporating network embedding into Markov random field for better community detection[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2019, 33: 160-167.
2	陈洁, 李锐, 赵姝, 等. 面向图表示社区检测的新型聚类覆盖算法[J]. 电子学报, 2020, 48(9): 1680-1687.
	CHEN J, LI R, ZHAO S, et al. A new clustering cover algorithm based on graph representation for community detection[J]. Acta Electronica Sinica, 2020, 48(9): 1680-1687. (in Chinese)
3	MATSUGU S, SHIOKAWA H, KITAGAWA H. Fast algorithm for attributed community search[J]. Journal of Information Processing, 2021, 29: 188-196.
4	潘剑飞, 董一鸿, 陈华辉, 等. 基于结构紧密性的重叠社区发现算法[J]. 电子学报, 2019, 47(1): 145-152.
	PAN J F, DONG Y H, CHEN H H, et al. The overlapping community discovery algorithm based on compact structure[J]. Acta Electronica Sinica, 2019, 47(1): 145-152. (in Chinese)
5	马慧芳, 陈海波, 赵卫中, 等. 融合标签平均划分距离和结构关系的微博用户可重叠社区发现[J]. 电子学报, 2018, 46(11): 2612-2618.
	MA H F, CHEN H B, ZHAO W Z, et al. Leveraging tag mean partition distance and social structure for overlapping microblog user community detection[J]. Acta Electronica Sinica, 2018, 46(11): 2612-2618. (in Chinese)
6	LEE J Y, LEE J. Hidden information revealed by optimal community structure from a protein-complex bipartite network improves protein function prediction[J]. PLoS One, 2013, 8(4): e60372.
7	FANG Y X, HUANG X, QIN L, et al. A survey of community search over big graphs[J].The VLDB Journal, 2020, 29(1): 353-392.
8	AGHAALIZADEH S, AFSHORD S T, BOUYER A, et al. A three-stage algorithm for local community detection based on the high node importance ranking in social networks[J]. Physica A: Statistical Mechanics and Its Applications, 2021, 563: 125420.
9	於志勇, 陈基杰, 郭昆, 等. 基于影响力与种子扩展的重叠社区发现[J]. 电子学报, 2019, 47(1): 153-160.
	YU Z Y, CHEN J J, GUO K, et al. Overlapping community detection based on influence and seeds extension[J]. Acta Electronica Sinica, 2019, 47(1): 153-160. (in Chinese)
10	AKOGLU L, TONG H H, MEEDER B, et al. PICS: parameter-free identification of cohesive subgroups in large attributed graphs[C]//Proceedings of the 2012 SIAM International Conference on Data Mining. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2012: 439-450.
11	SHANG J W, WANG C K, WANG C P, et al. An attribute-based community search method with graph refining[J].The Journal of Supercomputing, 2020, 76(10): 7777-7804.
12	LIU H J, MA H F, CHANG Y, et al. Leveraging User Preferences for Community Search via Attribute Subspace[M]//Knowledge Science, Engineering and Management. Cham: Springer International Publishing, 2019: 584-595.
13	FANG Y X, CHENG R, LUO S Q, et al. Effective community search for large attributed graphs[J]. Proceedings of the VLDB Endowment, 2016, 9(12): 1233-1244.
14	LIU Q, ZHU Y F, ZHAO M J, et al. VAC: vertex-centric attributed community search[C]//2020 IEEE 36th International Conference on Data Engineering. Piscataway: IEEE, 2020: 937-948.
15	YE W, MAUTZ D, BÖHM C, et al. Incorporating user's preference into attributed graph clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 33(12): 3716-3728.
16	PEROZZI B, AKOGLU L, SÁNCHEZ P I, et al. Focused clustering and outlier detection in large attributed graphs[C]//KDD'14: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, USA: ACM, 2014: 1346-1355.
17	WU P, PAN L. Mining target attribute subspace and set of target communities in large attributed networks[EB/OL]. (2017-05-10). .
18	LI Y, SHA C F, HUANG X, et al. Community detection in attributed graphs: An embedding approach[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2018, 32(1): 338-345
19	DE MÁNTARAS R L. A distance-based attribute selection measure for decision tree induction[J].Machine Learning, 1991, 6(1): 81-92.
20	马慧芳, 张迪, 赵卫中, 等. 基于超图随机游走标签扩充的微博推荐方法[J]. 软件学报, 2019, 30(11): 3397-3412.
	MA H F, ZHANG D, ZHAO W Z, et al. Microblog recommendation method based on hypergraph random walk tag extension[J]. Journal of Software, 2019, 30(11): 3397-3412. (in Chinese)
21	SEIDMAN S B. Network structure and minimum degree[J]. Social Networks, 1983, 5(3): 269-287.
22	EBADIAN S, HUANG X. Fast algorithm for K-truss discovery on public-private graphs[C]//Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2019: 2258-2264.
23	WU J, LI C M, JIANG L, et al. Local search for diversified Top-k clique search problem[J]. Computers & Operations Research, 2020, 116: 104867.
24	GIATSIDIS C, BERBERICH K, THILIKOS D M, et al. Visual exploration of collaboration networks based on graph degeneracy[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM,2012: 1512-1515.
25	AYDIN K, BATENI M, MIRROKNI V. Distributed balanced partitioning via linear embedding[C]//WSDM'16: Proceedings of the Ninth ACM International Conference on Web Search and Data Mining. New York, USA: ACM,2016: 387-396.

数据集	节点	边	μ	属性
Synth 1	1500	34950	0.1	{f₁,f₂,f₃,f₄, _,f₅,f₆}
Synth 2	8000	11853	0.15	{f₇,f₈,f₉}

数据集	节点	边	μ	属性
Synth 1	1500	34950	0.1	{f₁,f₂,f₃,f₄, _,f₅,f₆}
Synth 2	8000	11853	0.15	{f₇,f₈,f₉}

数据集	节点数	边数	属性数	社区数
4Area	26144	108550	4	50
YouTube	77381	367151	30087	8385
Disney	124	333	28	9
Enron	13533	176967	18	40
IMDB	862	4388	21	30

数据集	节点数	边数	属性数	社区数
4Area	26144	108550	4	50
YouTube	77381	367151	30087	8385
Disney	124	333	28	9
Enron	13533	176967	18	40
IMDB	862	4388	21	30

方法	评价指标	4Area	YouTube	Disney	Enron	IMDB	Synth 1	Synth 2
FocusCO	Precision	0.687	0.662	0.749	0.692	0.726	0.738	0.712
FocusCO	CAS	0.532	0.514	0.598	0.543	0.571	0.581	0.558
TSCM	Precision	0.721	0.699	0.793	0.742	0.783	0.788	0.759
TSCM	CAS	0.546	0.531	0.593	0.556	0.582	0.582	0.567
ACQ	Precision	0.799	0.779	0.847	0.805	0.829	0.834	0.816
ACQ	CAS	0.576	0.557	0.628	0.588	0.611	0.607	0.594
λVAC-Ecore	Precision	0.804	0.792	0.847	0.817	0.842	0.841	0.819
λVAC-Ecore	CAS	0.442	0.429	0.514	0.451	0.507	0.483	0.465
LOCLU	Precision	0.866	0.849	0.911	0.879	0.901	0.901	0.867
LOCLU	CAS	0.601	0.584	0.657	0.611	0.638	0.642	0.623
IPCSO	Precision	0.899	0.879	0.931	0.909	0.916	0.929	0.917
IPCSO	CAS	0.647	0.632	0.694	0.651	0.617	0.689	0.671

属性网络中结合用户偏好的社区搜索和离群点检测

Incorporating User Preference for Community Search and Outlier Detection in Attributed Network

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 25

相关文章 7

编辑推荐

Metrics

[1]	李青青, 马慧芳, 李举, 李志欣. 属性网络中相似性增强随机游走的多社区搜索[J]. 电子学报, 2021, 49(11): 2096-2100.
[2]	杨晓玲, 冯山, 袁钟. 基于相对距离的反k近邻树离群点检测[J]. 电子学报, 2020, 48(5): 937-945.
[3]	彭涛, 杨妮亚, 徐原博, 王冰冰, 刘露. 双类型异质网中基于排序和聚类的离群点检测方法[J]. 电子学报, 2018, 46(2): 281-288.
[4]	杨金鸿, 邓廷权. 一种基于单簇核PCM的SVDD离群点检测方法[J]. 电子学报, 2017, 45(4): 813-819.
[5]	高志奇, 陶海红, 赵继超. 基于联合稀疏功率谱恢复的机载雷达稳健STAP算法研究[J]. 电子学报, 2016, 44(11): 2796-2801.
[6]	江峰;杜军威;葛艳;眭跃飞;曹存根. 基于粗糙集理论的序列离群点检测[J]. 电子学报, 2011, 39(2): 345-350.
[7]	江峰;眭跃飞;曹存根. 基于边界和距离的离群点检测[J]. 电子学报, 2010, 38(3): 700-705.