Abstract
Information recommendation between different user groups has recently received a lot of attention in the information service community. However, we find that obtaining the exact optimal recommendation solution is an NP-hard problem. Based on the above finding, in this paper, we present an efficient method achieving approximate optimal recommendation solution (AAORS) to reduce this NP-hard problem to an equivalent extended Steiner tree problem and obtain the approximate optimal recommendation solution appIRS in polynomial time. We theoretically prove that the global trust value of appIRS is at least 63 % of that obtained for the exact optimal solution optIRS. Moreover, in real applications, based on a computed index of reputation gain, we also adjust the recommendation solution produced by the AAORS method in polynomial time and obtain the optimal recommendation solution which satisfies the global reputation constraint. The detailed theoretical analyses and extensive experiments demonstrate that our proposed methods are both efficient and effective.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baglioni, M.; Geraci, F.; Pellegrini, M.; Lastres, E.: Fast exact computation of betweenness centrality in social networks. In: Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 450–456 (2012)
Hassan, S.; Sanger, J.; Pernul, G.; SoDA: dynamic visual analytics of big social data. In: Proceedings of the International Conference on Big Data and Smart Computing, pp. 183–188 (2014)
Lilac A., Dalal A., Wejdan A.: A comparison between ontology-based and translation-based semantic search engines for arabic blogss. Arab. J. Sci. Eng. 38(11), 2985–2992 (2013)
Gong, X.; Chen, X.; Zhang, J.: Social group utility maximization game with applications in mobile social networks. In: Proceedings of the 51st Annual Allerton Conference on the Communication, Control, and Computing, pp. 1496–1500 (2013)
Xiang, R.; Neville, J.; Rogati, M.: Modeling relationship strength in online social network. In: Proceedings of the 19th International Conference on World Wide Web, pp. 981–990 (2010)
Borgatti S.P., Mehra A., Brass D.J.: Network analysis in the social sciences. Science 323(5916), 892–895 (2009)
Amershi, S.; Fogarty, J.; Weld, D.: Regroup: interactive machine learning for on-demand group creation in social networks. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pp. 21–30 (2012)
Gimenes, G.P.; Gualdron, H.; Raddo, T.R.; Rodrigues, J.F.: Supervised-learning link recommendation in the DBLP co-authoring network. In: Proceedings of IEEE International Conference on Pervasive Computing and Communications Workshops, pp. 563–568 (2014)
Semenov, A.; Veijalainen, J.; Hajeer, M.; Dasgupta, D.: Political communities in Russian portion of LiveJournal. In: Proceedings of International Conference on Computational Science and Computational Intelligence, pp. 314–319 (2014)
Backstrom, L.; Huttenlocher, D.; Kleinberg, J.: Group formation in large social networks: membership, growth, and evolution. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 44–54 (2006)
Wang X., Kwon T., Choi Y., Chen M., Zhang Y.: Characterizing the gaming traffic of world of Warcraft: from game scenarios to network access technologies. IEEE Netw. 26(1), 27–34 (2012)
Patil, A.; Liu, J.; Gao, J.: Predicting group stability in online social networks. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 1021–1030 (2013)
Sagar, A.B.: Dependability of social network groups. In: Proceedings of the CUBE International Information Technology Conference, pp. 694–700 (2012)
Banerjee A., Dutta P., Ghosh S.: Experience based energy efficient reactive routing protocol (EXERP) for mobile ad-hoc networks. Arab. J. Sci. Eng. 39(2), 891–901 (2014)
Li, C.T.; Shan, M.K.: Composing activity groups in social networks. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp. 2375–2378 (2012)
Liang D., Ma S.: An extended Steiner tree optimization problem and its applications. Chin. J. Comput. 19(12), 895–902 (1996)
Mislove, A.; Marcon, M.; Gummadi, K.P.: Measurement and analysis of online social networks. In: Proceedings of the 7th ACM SIGCOMM Conference on Internet measurement, pp. 29–42 (2007)
Sabater J., Sierra C.: Review on computational trust and reputation models. Artif. Intell. Rev. 24(1), 33–60 (2005)
Unnikrishnan, J.; Naini, F.M.: De-anonymizing private data by matching statistics. In: Proceedings of the 51st Annual Allerton Conference on Communication, Control, and Computing, pp. 1616–1623 (2013)
Kannadhasan, S.; KarthiKeyan, G.; Sethupathi, V.: A graph theory based energy efficient clustering techniques in wireless sensor networks. In: Proceedings of the IEEE Conference on Information and Communication Technologies, pp. 151–155 (2013)
Saatci, E.; Akan, A.: Generalized Gauss distribution noise model for respiratory parameter estimation. In: Proceedings of the 17th Signal Processing and Communications Applications Conference, pp. 141–144 (2009)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Huang, Z., Zhang, J. & Zhang, B. Information Recommendation Between User Groups in Social Networks. Arab J Sci Eng 40, 1443–1453 (2015). https://doi.org/10.1007/s13369-015-1615-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13369-015-1615-z