Skip to main content
Springer Nature Link
Log in

Multi-fuzzy-objective graph pattern matching in big graph environments with reliability, trust and social relationship

  • Published:
World Wide Web Aims and scope Submit manuscript

Abstract

With the advent of the era of big data, the scale of data has grown dramatically, and there is a close correlation between massive multi-source heterogeneous data, which can be visually depicted by a big graph. Big graph, especially from Web data, social networks, or biometric data, has attracted more and more attention from researchers, which usually contains complex relationships and multiple attributes. How to perform efficient query and matching on big graph data is the basic problem on analyzing big graph. Using multi-constrained graph pattern matching, we can design patterns that meet our specific requirements, and find matched subgraphs to locate the required patterns to accomplish specific tasks. So how to find matched subgraphs with good attributes in big graph becomes the key problem on big graph research. Considering the possibility that a node in a subgraph may fail due to reliability, in order to select more and better matched subgraphs, in this paper, we introduce fuzziness and reliability into multi-objective graph pattern matching, and then use a multi-objective genetic algorithm NSGA-II to find the subgraphs with higher reliability and better attributes including social trust and social relationship. Finally, a reliability-based multi-fuzzy-objective graph pattern matching method (named as RMFO-GPM) is proposed. The experimental results on real data sets show the effectiveness of the proposed RMFO-GPM method comparing with other state-of-art methods.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9

Similar content being viewed by others

References

  1. Bai, Y., Wang, C., Ying, X.: Para-G: Path Pattern Query Processing on Large Graphs. World Wide Web Journal. 20(3), 515–541 (2017)

    Article  Google Scholar 

  2. Brynielsson, J., Högberg, J., Kaati, L., Mårtenson, C., Svenson, P.: Detecting Social Positions using Simulation. International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2010). pp. 48–55 (2010)

  3. Chen, J.: Survival Analysis and Reliability (in Chinese). Peking University Press (2005)

  4. Cheng, J., Yu, J. X., Ding, B., Yu, P. S., Wang, H.: Fast Graph Pattern Matching. IEEE International Conference on Data Engineering (ICDE 08). pp. 913–922 (2008)

  5. Cheng, J., Zeng, X., & Yu, J.X.: Top-K Graph Pattern Matching Over Large Graphs. 2013 IEEE 29th International Conference on Data Engineering (ICDE 2013). pp. 1033–1044 (2013)

  6. Choudhury, S., Holder, L., Chin, G., Ray, A., Beus, S., Feo, J.: StreamWorks - A system for Dynamic Graph Search. ACM SIGMOD International Conference on Management of Data (SIGMOD 13). pp. 1101–1104 (2013)

  7. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)

    Article  Google Scholar 

  8. Fan, W., Li, J., Ma, S., Tang, N., Wu, Y., Wu, Y.: Graph Pattern Matching: from Intractable to Polynomial Time. Proceedings of the VLDB Endowment. 3(1–2), 264–275 (2010)

    Article  Google Scholar 

  9. Fan, W., Li, J., Luo, J., Tan, Z., Wang, X., Wu, Y.: Incremental Graph Pattern Matching. ACM SIGMOD International Conference on Management of Data (SIGMOD 11). pp. 925–936 (2011)

  10. Fan, W., Wang, X., Wu, Y.: Diversified Top-K Graph Pattern Matching. Proceedings of the VLDB Endowment. 6(13), 1510–1521 (2013)

    Article  Google Scholar 

  11. Henzinger, M.R.: Computing Simulations on Finite and Infinite Graphs. 36th Annual Symposium on Foundations of Computer Science (FOCS 95). pp. 453 (2002)

  12. Li, L., Wang, Y., Context Based Trust Normalization in Service-Oriented Environments. International Conference on Autonomic and Trusted Computing (ATC 2010). pp. 122–138 (2010)

    Google Scholar 

  13. Li, L., Wang, Y., Varadharajan, V.: Fuzzy Regression Based Trust Prediction in Service-Oriented Applications. International Conference on Autonomic and Trusted Computing (ATC-09). pp. 221–235 (2009)

    Google Scholar 

  14. Li, L., Chu, Y., Wang, M., Han, L., Wu, X.: NSGA-II-based Multi-label Seed Node Selection in Network Environments (in Chinese). J Electron Inf Technol. 39(9), 2040–2047 (2017)

    Google Scholar 

  15. Li, L., Zhou, C., He, J., Wang, J., Li, X., Wu, X.: Collective Semantic Behavior Extraction in Social Networks. J Comput Sci. 28(2018), 236–244 (2018)

    Article  Google Scholar 

  16. Li, L., Li, A., Wang, M., Wu, X.: Social Network based Behavior Analysis and Mining, Science Publishing, 2018

  17. Liu, G., Wang, Y., Orgun, M.A.: Optimal Social Trust Path Selection in Complex Social Networks, Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI10), pp. 1391–1398 (2010)

  18. Liu, G., Wang, Y., Orgun, M.A.: Finding K Optimal Social Trust Paths for the Selection of Trustworthy Service Providers in Complex Social Networks. IEEE Trans. Serv. Comput. 6(2), 152–167 (2013)

    Article  Google Scholar 

  19. Liu, G., Zheng, K., Wang, Y., Orgun, M. A., Liu, A., Zhao, L., Zhou, X. F.: Multi-constrained Graph Pattern Matching in Large-scale Contextual Social Graphs. IEEE International Conference on Data Engineering (ICDE 2015). pp.351–362 (2015)

  20. Liu, G., Liu, Y., Zheng, K., Liu, A., Li, Z., Wang, Y., Zhou, X.: MCS-GPM: Multi-Constrained Simulation Based Graph Pattern Matching in Contextual Social Graphs. IEEE Trans. Knowl. Data Eng. 30(6), 1050–1064 (2018)

    Article  Google Scholar 

  21. Liu, A., Wang, W., Shang, S., Li, Q., Zhang, X.: Efficient Task Assignment in Spatial Crowdsourcing with Worker and Task Privacy Protection. GeoInformatica. 22(2), 335–362 (2018)

    Article  Google Scholar 

  22. Liu, G., Shi, Q., Zheng, K., Liu, A., Li, Z., Zhou, X.: An Efficient Method for Top-k Graph based Node Matching, World Wide Web Journal, In Press (2019)

  23. Liu, G., Shi, Q., Zheng, K., Li, Z., Liu, A., Xu, J.: Context-aware Graph Pattern based Top-k Designated Nodes Finding in Social Graphs. World Wide Web Journal. 22(2), 751–770 (2019)

    Article  Google Scholar 

  24. Ma, S., Cao, Y., Fan, W., Huai, J., Wo, T.: Strong Simulation: Capturing Topology in Graph Pattern Matching. ACM Trans. Database Syst. 39(1), 1–46 (2014)

    Article  MathSciNet  Google Scholar 

  25. Parton, N.: Reflections on the Social Construction of Reality: a Treatise in the Sociology of Knowledge. Gynecol. Oncol. 131(2), 400–403 (2009)

    Google Scholar 

  26. Shi, Q., Liu, G., Zheng, K., Liu, A., Li, Z., & Zhao, L., et al.: Multi-constrained Top-K Graph Pattern Matching in Contextual Social Graphs. 2017 IEEE International Conference on Web Services (ICWS 2017). pp. 588–595 (2017)

  27. Srinivas, N., & Deb, K.: Multi-objective Optimization Using Non-dominated Sorting in Genetic Algorithms. MIT Press (1994)

  28. Sun, Z., Wang, H., Wang, H., Shao, B., Li, J.: Efficient Subgraph Matching on Billion Node Graphs. Proceedings of the VLDB Endowment. 5(9), 788–799 (2012)

    Article  Google Scholar 

  29. Tang, D., Zhang, Y., He, Y.: Research and Application on Crime Rule based on Graph Data Mining Algorithm (in Chinese). J Comput Technol Dev. 21(11), 89–91 (2011)

    Google Scholar 

  30. Tong, H., Faloutsos, C., Gallagher, B., & Eliassi-Rad, T.: Fast Best-effort Pattern Matching in Large Attributed Graphs. ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 07). pp. 737–746 (2007)

  31. Wang, X., Lv, Z., Tang, Z.: Multi-objective Dynamic Optimal Dispatching of Grid-connected Microgrid based on Tou Power Price Mechanism (in Chinese). Power System Protection & Control. 45(4), 9–18 (2017)

    Google Scholar 

  32. Xiao, M., Wu, J., Huang, L., Cheng, R., Wang, Y.: Online Task Assignment for Crowdsensing in Predictable Mobile Social Networks. IEEE Trans. Mob. Comput. 16(8), 2306–2320 (2017)

    Article  Google Scholar 

  33. Xiao, M., Ma, K., Liu, A., Zhao, H., Li, Z., Zheng, K., Zhou, X.: SRA: Secure Reverse Auction for Task Assignment in Spatial Crowdsourcing. IEEE Trans. Knowl. Data Eng. (2019). https://doi.org/10.1109/TKDE.2019.2893240

  34. Zhai, D., Sun, Y., Liu, A., Li, Z., Liu, G., Zhao, L., Zheng, K.: Towards Secure and Truthful Task Assignment in Spatial Crowdsourcing. World Wide Web Journal. 1–24 (2019). https://doi.org/10.1007/s11280-018-0638-2

    Article  Google Scholar 

  35. Zhang, T., Gao, Y., Qiu, L., Chen, L., Linghu, Q., Pu, S.: Distributed Time-respecting Flow Graph Pattern Matching on Temporal Graphs, World Wide Web Journal, In Press (2019)

  36. Zhu, J., Jiang, W., Liu, A., Liu, G., Zhao, L.: Effective and Efficient Trajectory Outlier Detection based on Time-dependent Popular Route. World Wide Web Journal. 20(1), 111–134 (2017)

    Article  Google Scholar 

Download references

Acknowledgements

This work has been supported by the National Key Research and Development Program of China under grant 2016YFB1000901, the National Natural Science Foundation of China under grants 91746209 & 61673152, the Program for Changjiang Scholars and Innovative Research Team in University (PCSIRT) of the Ministry of Education of China under grant IRT17R32, and the Fundamental Research Funds for the Central Universities under grant JZ2019HGBH0201.

Author information

Authors and Affiliations

  1. Key Laboratory of Knowledge Engineering with Big Data (Hefei University of Technology) and School of Computer Science and Information Engineering, Hefei University of Technology, Hefei, China

    Lei Li, Fang Zhang, Zan Zhang, Peipei Li & Chenyang Bu

Authors
  1. Lei Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fang Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zan Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Peipei Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Chenyang Bu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zan Zhang.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article belongs to the Topical Collention: Special Issue on Trust, Privacy, and Security in Crowdsourcing Computing

Guest Editors: An Liu, Guanfeng Liu, Mehmet A. Orgun, and Qing Li

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, L., Zhang, F., Zhang, Z. et al. Multi-fuzzy-objective graph pattern matching in big graph environments with reliability, trust and social relationship. World Wide Web 23, 649–669 (2020). https://doi.org/10.1007/s11280-019-00714-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11280-019-00714-9

Keywords

Search

Navigation