Multi-Fuzzy-Objective Graph Pattern Matching with Big Graph Data

Multi-Fuzzy-Objective Graph Pattern Matching with Big Graph Data

Lei Li (Key Laboratory of Knowledge Engineering with Big Data (Hefei University of Technology), Hefei, China & School of Computer Science and Information Engineering, Hefei University of Technology, Hefei, China), Fang Zhang (Zhongxing Telecommunication Equipment Corporation, Nanjing, China) and Guanfeng Liu (Macquarie University, Sydney Australia)
Copyright: © 2019 |Pages: 17
DOI: 10.4018/JDM.2019100102

Abstract

Big graph data is different from traditional data and they usually contain complex relationships and multiple attributes. With the help of graph pattern matching, a pattern graph can be designed, satisfying special personal requirements and locate the subgraphs which match the required pattern. Then, how to locate a graph pattern with better attribute values in the big graph effectively and efficiently becomes a key problem to analyze and deal with big graph data, especially for a specific domain. This article introduces fuzziness into graph pattern matching. Then, a genetic algorithm, specifically an NSGA-II algorithm, and a particle swarm optimization algorithm are adopted for multi-fuzzy-objective optimization. Experimental results show that the proposed approaches outperform the existing approaches effectively.
Article Preview
Top

Introduction

Since the concept of Big Data has been proposed by the paper Big data: How do your data grow? published in Sep 2008 at Nature (Lynch, 2008), Big data have become the focus of both academics and industry. Recently, the rising and popularity of new network applications, such as composite services, social networks, biological networks and internet of things, on the one hand, increase the velocity and scale of the data generation (Li et al., 2016); on the other hand, these lead to a dramatic promotion of the complexity of big data processing and analyzing. The intricate relationship between data makes the processing complexity of big data involving network structures and data connections (named big graph data) become exponential. In addition to the exponential increase of data scale, this leads to a double exponential increase of complexity of big graph data processing and analyzing. However, there is a significant leap between this situation and the current slow increase of big graph data storage and computation. Hence, it is a common basic problem for big graph data computation that how to effectively and efficiently process and analyze big graph data. Sophisticated analysis and intelligent understanding of big graph data have become an important bottleneck for big graph data cognition and value mining.

Big graph, particularly composite service or social network attracts more and more attention from scholars, where one of the most important research areas is graph pattern matching, especially with big graph data. With the help of graph pattern matching, we can design a pattern graph satisfying special personal requirements, and locate the subgraphs which match the required pattern, which can finish the required task with the matched subgraph, such as: social status detection (Cheng et al., 2008), expert finding (Cheng et al., 2013; Tong et al., 2007), travel planning (Tong et al., 2007), research group selection, and etc. Big graph data are different from traditional data with a simple relation, and they usually contain complex relationship. For example, in composite service, vertices represent services, such as selling a product online (i.e., the traditional online service), or a functional component implemented by using Web service technologies, edges represent the relation of services, and together they can function as a whole; in social networks, vertices represent participants, and edges represent social relations which can be friendship or working relationship in real, co-authorship of a paper, or superior-subordinate relationship etc. In addition, vertices or edges can have some attribute information, such as the vertex of a social contextual graph (Henzinger et al., 2002) can have the information about social roles, and its edge can have attribute information about social trust and social intimacy. Generally, this rich metadata information of big graph data enriches the description of the data in a wide range of contextual information, such as source, time, occurrence probability, and other related metadata about the data (Li et al., 2015), which is significant for the subsequent data processing. Taking big graph data related to medical issues as an example, due to difference of medical equipment and software, and personal experience of doctors and other reasons, the data collected by certain medical institutions may be taken as untrustworthiness by others. These data with different attributes can produce intricate correlations and then converge and form a big graph. Then, how to locate a graph pattern with certain attributes in the big graph effectively and efficiently becomes a key problem to analyze and deal with big graph data, especially for a specific domain (Pienta et al., 2014).

The major contribution of the paper can be summarized as follows:

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 31: 4 Issues (2020): Forthcoming, Available for Pre-Order
Volume 30: 4 Issues (2019)
Volume 29: 4 Issues (2018)
Volume 28: 4 Issues (2017)
Volume 27: 4 Issues (2016)
Volume 26: 4 Issues (2015)
Volume 25: 4 Issues (2014)
Volume 24: 4 Issues (2013)
Volume 23: 4 Issues (2012)
Volume 22: 4 Issues (2011)
Volume 21: 4 Issues (2010)
Volume 20: 4 Issues (2009)
Volume 19: 4 Issues (2008)
Volume 18: 4 Issues (2007)
Volume 17: 4 Issues (2006)
Volume 16: 4 Issues (2005)
Volume 15: 4 Issues (2004)
Volume 14: 4 Issues (2003)
Volume 13: 4 Issues (2002)
Volume 12: 4 Issues (2001)
Volume 11: 4 Issues (2000)
Volume 10: 4 Issues (1999)
Volume 9: 4 Issues (1998)
Volume 8: 4 Issues (1997)
Volume 7: 4 Issues (1996)
Volume 6: 4 Issues (1995)
Volume 5: 4 Issues (1994)
Volume 4: 4 Issues (1993)
Volume 3: 4 Issues (1992)
Volume 2: 4 Issues (1991)
Volume 1: 2 Issues (1990)
View Complete Journal Contents Listing