Abstract
Graph Pattern Matching (GPM) plays a significant role in many real applications, where many applications often need to find Top-K matches of a specific node, (named as the designated node vd) based on a pattern graph, rather than the entire set of matching. However, the existing GPM methods for matching the designated node vd in social graphs do not consider the social contexts like the social relationships, the social trust and the social positions which commonly exist in real applications, like the experts recommendation in social graphs, leading to deliver low quality designated nodes. In this paper, we first propose the conText-Aware Graph pattern based Top-K designed nodes finding problem (TAG-K), which involves the NP-Complete Multiple Constrained GPM problem, and thus it is NP-Complete. To address the efficiency and effectiveness issues of TAG-K in large-scale social graphs, we propose two indices, MA-Tree and SSC-Index, which can help efficiently find the Top-K matching. Furthermore, we propose an approximation algorithm, A-TAG-K. Using real social network datasets, we experimentally verify that A-TAG-K outperforms the existing methods in both efficiency and effectiveness for solving the TAG-K problem.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Berger, P., Luckmann, T.: The Social Construction of Reality: A Treatise in the Sociology of Knowledge. Anchor Books, New York (1966)
Biggs, N., Lloyd, E., Wilson, R.: Graph Theory. Oxford University Press, Oxford (1986)
Chang, L., Lin, X., Zhang, W., Yu, J.X., Zhang, Y., Qin, L.: Optimal enumeration: efficient top-k tree matching. VLDB 8(5), 533–544 (2015)
Chevalier, F., Domenger, J.P., Pineau, J.B., Delest, M.: Retrieval of objects in video by similarity based on graph matching. Pattern Recogn. Lett. 28(8), 939–949 (2007)
Cohen, S., Kimelfeld, B., Koutrika, G., Jan, V.: On principles of egocentric person search in social networks. In: Workshop on VLDS, pp 3–6 (2011)
Demuth, H.B., Beale, M.H., Jess, O.D., Hagan, T.M.: Neural Network Design. Martin Hagan Press (2014)
Ding, X., Jia, J., Li, J., Liu, J., Jini, H.: Top-k similarity matching in large graphs with attributes. In: DASFAA, pp 156–170 (2014)
Eppstein, D.: Finding the k shortest paths. SIAM J. Comput. 28(2), 652–673 (1998)
Fan, W., Li, J., Wang, X., Wu, Y.: Query preserving graph compression. In: SIGMOD’12, pp 157–168 (2012)
Fan, W., Wang, X., Wu, Y.: Diversified top-k graph pattern matching. VLDB 6(13), 1510–1521 (2013)
Fani, W., Li, J., Ma, S., Tang, N., Wu, Y., Wu, Y.: Graph pattern matching: from intractable to polynomial time. VLDB 3(1-2), 264–275 (2010)
Lappas, T., Liu, K., Terzi, E.: A survey of algorithms and systems for expert location in social networks. In: Social Network Data Analytics, pp 215–241 (2011)
Liu, G., Wang, Y., Orgun, M.A.: Trust transitivity in complex social networks. In: AAAI, pp 1222–1229 (2011)
Liu, G., Wang, Y., Orgun, M.A.: Social context-aware trust network discovery in complex contextual social networks. In: AAAI, vol. 12, pp 101–107 (2012)
Liu, G., Wang, Y., Orgun, M.A., et al.: Optimal social trust path selection in complex social networks. In: AAAI, pp 1397–1398 (2010)
Liu, G., Wang, Y., Orgun, M.A., Lim, E.P.: Finding the optimal social trust path for the selection of trustworthy service providers in complex social networks. IEEE Transactions on Services Computing (TSC) 6(2), (2013)
Liu, G., Zheng, K., Wang, Y., Orgun, M.A., Liu, A., Zhao, L., Zhou, X.: Multi-constrained graph pattern matching in large-scale contextual social graphs. In: ICDE, pp 351–362 (2015)
Liu, G., Zheng, K., Wang, Y., Orgun, M.A., Liu, A., Zhao, L., Zhou, X.: Multi-constrained graph pattern matching in large-scale contextual social graphs. In: ICDE’15, pp 351–362 (2015)
Milano, R., Baggio, R., Piattelli, R.: The effects of online social media on tourism websites. In: ENTER, pp 471–483 (2011)
Modiano, E.: Traffic grooming in wdm networks. IEEE Commun. Mag. 39(7), 124–129 (2001)
Morris, M.R., Teevan, J., Panovich, K.: What do people ask their social networks, and why?: a survey study of status message q&a behavior. In: CHI., pp 1739–1748 (2010)
Rauch, M., Thomas, H., Peter, K.: Computing simulations on finite and infinite graphs. In: Annual Symposium o Foundations of Computer Science, pp 453–462 (1995)
Raymond, W.J., Willett, P.: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J. Comput. Aided Mol. Des. 16(7), 521–533 (2002)
Schenkel, R., Crecelius, T., Kacimi, M., Michel, S., Neumann, T., Parreira, J., Weikum, G.: Efficient top-k querying over social-tagging networks. In: SIGIR, pp 523–530 (2008)
Song, J., Gao, L., Liu, L., Zhu, X., Sebe, N.: Quantization-based hashing: a general framework for scalable image and video retrieval. Pattern Recogn. 75, 175–187 (2018)
Song, J., Gao, L., Nie, F., Shen, H.T., Sebe, N.: Optimized graph learning using partial tags and multiple features for image and video annotation. IEEE Trans. Image Process. 25(11), 4999–5011 (2016)
Song, J., Shen, H.T., Wang, J., Huang, Z., Sebe, N., Wang, J.: A distance-computation-free search scheme for binary code databases. IEEE Trans. Multimedia 18(3), 484–495 (2016)
Tang, J., Zhang, J., Yan, L., Li, J., Zhang, L., Su, Z.: Arnetminer: Extraction and mining of academic social networks. In: KDD, pp 990–998 (2008)
Tian, Y., Patel, P.M.: Tale: A tool for approximate large graph matching. In: ICDE, pp 963–972 (2008)
Ullmann, R.J.: An algorithm for subgraph isomorphism. J. ACM 23(1), 31–42 (1976)
Wang, J., Zhang, T., Song, J., Sebe, N., Shen, H.T.: A survey on learning to hash. IEEE TPAMI August(99), 1–1 (2017)
Yildirim, H., Chaoji, V., Zaki, M.J.: Grail: Scalable reachability index for large graphs. In: VLDB, pp 276–284 (2010)
Yoo, S., Yang, Y., Lin, F., Moon, I.: Mining social networks for personalized email prioritization. In: KDD, pp 967–976 (2009)
Zhu, X., Zhang, L., Huang, Z.: A sparse embedding and least variance encoding approach to hashing. IEEE Trans. Image Process. 23(9), 3737 (2014)
Zhu, Y., Qin, L., Yu, J.X., Cheng, H.: Finding top-k similar graphs in graph databases. In: EDBT, pp 456–467 (2012)
Acknowledgments
This work was partially supported by Natural Science Foundation of China (Grant Nos. 61303019, 61572336, 61532018, 61402313, 61502324), Doctoral Fund of Ministry of Education of China (20133201120012), Postdoctoral Science Foundation of China (2015M571805, 2016T90492), Collaborative Innovation Center of Novel Software Technology and Industrialization, Jiangsu, China, and project supported by the Jiangsu Key Laboratory of Image and Video Understanding for Social Safety (Nanjing University of Science and Technology), Grant No. 30916014107.
Author information
Authors and Affiliations
Corresponding author
Additional information
This article belongs to the Topical Collection: Special Issue on Deep vs. Shallow: Learning for Emerging Web-scale Data Computing and Applications
Guest Editors: Jingkuan Song, Shuqiang Jiang, Elisa Ricci, and Zi Huangs
Rights and permissions
About this article
Cite this article
Liu, G., Shi, Q., Zheng, K. et al. Context-aware graph pattern based top-k designated nodes finding in social graphs. World Wide Web 22, 751–770 (2019). https://doi.org/10.1007/s11280-017-0513-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11280-017-0513-6