基于社区特征的平衡模块度最大化社交链接预测模型

doi:10.11896/j.issn.1002-137X.2019.03.038

Abstract

Abstract: Link prediction and community detection are the two major research directions in the field of social network analysis.It is of great significance to explore the community structure and improve the link prediction effect.Based on the modularity maximization link prediction model,this paper proposed a link prediction method based on community structure feature extraction and selection.Firstly,the community structure based similarity index and influence node identification method are introduced into the network evolution model to obtain and link the local and global features respectively.Then,the feature selection algorithm with minimum redundancy and maximum correlation is used to measure the mutual influence,andthe most expressive candidate features are filtered out.Finally,based on the above steps,the features are incorporated into the modularity maximization link prediction model.The algorithm was compared with related algorithms on both artificial and real datasets.The results verify the high efficiency of the algorithm and the necessity of feature extraction and selection based on community structure.

Key words: Community feature, Feature selection, Link prediction, Modularity, Social network

CLC Number:

TP391

WU Jie-hua,SHEN Jing,ZHOU Bei. Community Features Based Balanced Modularity Maximization Social Link Prediction Model[J].Computer Science, 2019, 46(3): 253-259.

References

[1]LAN M W,LI C P,WANG S Q,et al.Survey of Sign Prediction Algorithms in Signed Social Networks[J].Journal of Computer Research and Development,2015,52(2):410-422.(in Chinese)
蓝梦微,李翠平,王绍卿,等.符号社会网络中正负关系预测算法研究综述[J].计算机研究与发展,2015,52(2):410-422.
[2]WASSERMAN S,FAUST K.Social network analysis:Methods and applications[M].New York:Cambridge University Press,1994.
[3]PHILIP S Y,HAN J,FALOUTSOS C.Link mining:Models,algorithms,and applications[M].Berlin:Springer,2010.
[4]LIBENNOWELL D,KLEINBERG J.The linkprediction problem for social networks[J].Journal of the Association for Information Science and Technology,2007,58(7):1019-1031.
[5]ZHONG E,FAN W,ZHU Y,et al.Modeling the dynamics of composite social networks[C]∥Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2013:937-945.
[6]PEROZZI B,AL-RFOU R,SKIENA S.Deepwalk:Online lear-
ning of social representations[C]∥Proceedings of the 20th ACM SIGKDD International Conference on KnowledgeDisco-very and Data Mining.ACM,2014:701-710.
[7]DONG Y,TANG J,WU S,et al.Link Prediction and Recom-
mendation across Heterogeneous Social Networks[C]∥2012 IEEE 12th International Conference on Data Mining (ICDM).IEEE,2012:181-190.
[8]SYMEONIDIS P,IAKOVIDOU N,MANTAS N,et al.From bio-
logical to social networks:Link prediction based on multi-way spectral clustering[J].Data & Knowledge Engineering,2013,87(1):226-242.
[9]SUN Y,BARBER R,GUPTA M,et al.Co-author Relationship Prediction in Heterogeneous Bibliographic Networks[C]∥International Conference on Advances in Social Networks Analysis and Mining,Asonam.DBLP,2011:121-128.
[10]Lv L,ZHOU T.Link prediction in complex networks:A survey[J].Physica A:Statistical Mechanics and Its Applications,2011,390(6):1150-1170.
[11]WU J H.TAN Model For Ties Prediction in Social Networks[J].Journal of Computer Applications,2013,33(11):3134-3137.(in Chinese)
伍杰华.基于树状朴素贝叶斯模型的社会网络关系预测[J].计算机应用,2013,33(11):3134-3137.
[12]LIU W,Lv L.Link prediction based on local random walk[J].EPL (Europhysics Letters),2010,89(5):58007.
[13]LI R H,YU J X,LIU J.Link prediction:the power of maximal entropy random walk[C]∥Proceedings of the 20th ACM International Conference on Information and Knowledge Management.ACM,2011:1147-1156.
[14]LU L,PAN L,ZHOU T,et al.Toward link predictability of
complex networks[J].Proceedings of the National Academy of Sciences,2015,112(8):2325-2330.
[15]NEWMAN M E.Communities,modules and large-scale structure in networks[J].Nature Physics,2012,8(1),25-31.
[16]YAN B,GREGORY S.Finding missing edges in networks based on their community structure[J].Physical Review E,2012,85(5):056112.
[17]SOUNDARAJAN S,HOPCROFT J.Using community information to improve the precision of link prediction methods[C]∥Proceedings of the 21st International Conference on World Wide Web.ACM,2012:607-608.
[18]CANNISTRACI C V,ALANIS-LOBATO G,RAVASI T.From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J].Scienti-fic Reports.2013,3(4):1613.
[19]KEMP C,TENENBAUM J B,GRIFFITHS T L,et al.Learning systems of concepts with an infinite relational model[C]∥National Conference on Artificial Intelligence.AAAI Press,2006:381-388.
[20]PALLA K,KNOWLES D A,GHAHRAMANI Z.An infinite latent attribute model for network data[C]∥Proceedings of the 29th International Coference on International Conference on Machine Learning.Omnipress,2012:395-402.
[21]WU J,ZHANG G,REN Y.A balanced modularity maximization link prediction model in social networks[J].Information Processing & Management,2017,53(1):295-307.
[22]L L,CHEN D,REN X L,et al.Vital nodes identification in complex networks[J].Physics Reports,2016,650(1):1-63.
[23]GU Y R,ZHU Z Y.Node Ranking in Complex Networks Based on LeaderRank and Modes Similaritya[J].Journal of University of Electronic Science and Technology of China,2017,46(2):441-448.(in Chinese)
顾亦然,朱梓嫣.基于LeaderRank和节点相似度的复杂网络重要节点排序算法[J].电子科技大学学报,2017,46(2):441-448.
[24]CHEN D B,GAO H,L L,et al.Identifying influential nodes in large-scale directed networks:the role of clustering[J].PloS one,2013,8(10):e77455.
[25]GUYON I,ELISSEEFF A.An introduction to variable and feature selection[J].Journal of Machine Learning Research,2003,3(1):1157-1182.
[26]PENG H,LONG F,DING C.Feature Selection Based on Mutual Information:Criteria of Max-Dependency,Max-Relevance,and Min-Redundancy[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2005,27(8):1226-1238.
[27]BARABASI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.
[28]DOROGOVTSEV S N,MENDES J F.Evolution of networks[J].Advances in Physics,2002,51(4):1079-1187.
[29]SALES-PARDO M,GUIMERA R,MOREIRA A A,et al.Extracting the hierarchical organization of complex systems[J].Proceedings of the National Academy of Sciences,2007,104(39):15224-15229.
[30]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks [J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[31]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.
Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics Theory & Experiment,2008,2008(10):155-168.

Related Articles 15

[1]	SONG Jie, LIANG Mei-yu, XUE Zhe, DU Jun-ping, KOU Fei-fei. Scientific Paper Heterogeneous Graph Node Representation Learning Method Based onUnsupervised Clustering Level [J]. Computer Science, 2022, 49(9): 64-69.
[2]	HUANG Li, ZHU Yan, LI Chun-ping. Author’s Academic Behavior Prediction Based on Heterogeneous Network Representation Learning [J]. Computer Science, 2022, 49(9): 76-82.
[3]	WANG Jian, PENG Yu-qi, ZHAO Yu-fei, YANG Jian. Survey of Social Network Public Opinion Information Extraction Based on Deep Learning [J]. Computer Science, 2022, 49(8): 279-293.
[4]	LI Bin, WAN Yuan. Unsupervised Multi-view Feature Selection Based on Similarity Matrix Learning and Matrix Alignment [J]. Computer Science, 2022, 49(8): 86-96.
[5]	HU Yan-yu, ZHAO Long, DONG Xiang-jun. Two-stage Deep Feature Selection Extraction Algorithm for Cancer Classification [J]. Computer Science, 2022, 49(7): 73-78.
[6]	KANG Yan, WANG Hai-ning, TAO Liu, YANG Hai-xiao, YANG Xue-kun, WANG Fei, LI Hao. Hybrid Improved Flower Pollination Algorithm and Gray Wolf Algorithm for Feature Selection [J]. Computer Science, 2022, 49(6A): 125-132.
[7]	WEI Peng, MA Yu-liang, YUAN Ye, WU An-biao. Study on Temporal Influence Maximization Driven by User Behavior [J]. Computer Science, 2022, 49(6): 119-126.
[8]	YU Ai-xin, FENG Xiu-fang, SUN Jing-yu. Social Trust Recommendation Algorithm Combining Item Similarity [J]. Computer Science, 2022, 49(5): 144-151.
[9]	LI Yong, WU Jing-peng, ZHANG Zhong-ying, ZHANG Qiang. Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism [J]. Computer Science, 2022, 49(4): 43-48.
[10]	CHANG Ya-wen, YANG Bo, GAO Yue-lin, HUANG Jing-yun. Modeling and Analysis of WeChat Official Account Information Dissemination Based on SEIR [J]. Computer Science, 2022, 49(4): 56-66.
[11]	ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng. Budget-aware Influence Maximization in Social Networks [J]. Computer Science, 2022, 49(4): 100-109.
[12]	CHU An-qi, DING Zhi-jun. Application of Gray Wolf Optimization Algorithm on Synchronous Processing of Sample Equalization and Feature Selection in Credit Evaluation [J]. Computer Science, 2022, 49(4): 134-139.
[13]	SUN Lin, HUANG Miao-miao, XU Jiu-cheng. Weak Label Feature Selection Method Based on Neighborhood Rough Sets and Relief [J]. Computer Science, 2022, 49(4): 152-160.
[14]	GUO Lei, MA Ting-huai. Friend Closeness Based User Matching [J]. Computer Science, 2022, 49(3): 113-120.
[15]	LI Zong-ran, CHEN XIU-Hong, LU Yun, SHAO Zheng-yi. Robust Joint Sparse Uncorrelated Regression [J]. Computer Science, 2022, 49(2): 191-197.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Community Features Based Balanced Modularity Maximization Social Link Prediction Model

PDF (PC)