Effective Community Search Over Location-Based Social Networks: Conceptual Framework with Preliminary Result

Please download to get full document.

View again

of 14
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Similar Documents
Information Report
Category:

Presentations

Published:

Views: 0 | Pages: 14

Extension: PDF | Download: 0

Share
Description
Over the past decade, the volume of data has grown exponentially due to global internet service propagation. The number of individuals using the internet has expanded, especially with the use of social networks. Utilising GPS-enabled mobile devices,
Tags
Transcript
  Effective Community Search OverLocation-Based Social Networks: ConceptualFramework with Preliminary Result Ismail Alaqta 1 , 2 , Junho Wang 1 , and Mohammad Awrangjeb 1 1 School of Information and Communication Technology, Griffith University,Brisbane, Australia ismail.alaqta@@griffithuni.edu.au , { j.wang,m.awrangjeb } @griffith.edu.au 2 Department of Computer Science, Jazan University, Gizan, Saudi Arabia ialaqta@jazanu.edu.sa Abstract.  Over the past decade, the volume of data has grown ex-ponentially due to global internet service propagation. The number of individuals using the internet has expanded, especially with the use of social networks. Utilising GPS-enabled mobile devices, social networkshave been labelled Location-based Social Networks (LBSN). This serviceenables users to share their current spatial information by checking-inwith their friends at different locations. This article proposes a concep-tual framework to enhance the effectiveness of community search overLBSN. As users are more likely to look for people whom they sharesimilar personalities and interests, these keywords plus the spatial in-formation could help a lot in finding the most appropriate query-basedsocial community. As a result, this paper aims to contribute to the exist-ing body of knowledge as well as the industry in the field of communitysearch (CS). In particular, this work is focusing on CS in the environ-ment of LBSN to benefit from factors of spatial, keywords and time inorder to enhance community search models by these factors. Therefore,in this study, we focus on the current state-of-the art of CS and the limi-tations of integrated models. The preliminary results confirm that user’scheckins can present an alternative approach to produce and update theusers’ interests with which we use to boast effectiveness of attributedcommunity search along with spatial information. Keywords:  Community search  ·  User interests  ·  Spatial graph. 1 Introduction Over the past decade, the volume of data has grown exponentially due to globalinternet service propagation. According to the latest report issued by the UNs in-ternational telecommunications union (ITU), the number of individuals using theinternet exceeded 3.5 billion by 2017  3 . Social network applications, such as Face- 3 http://www.itu.int/en/ITU-D/statistics  2 I.Alaqta et al. book 4 , Twitter 5 and Foursquare 6 are the most common internet applications.These applications have consequently attracted millions of users. For example,over 1.75 billion of Facebook users are active monthly. 7 . Because they use GPS-enabled mobile devices, social networks have been called Location-based SocialNetworks (LBSNs). This service enables users to share their current spatial in-formation by checking-in with their friends at different locations. Foursquare, onwhich more than 30 million users are accommodated, receives millions of check-ins daily 8 . Other traditional social networks such as Facebook and Twitter 9 alsoprovide users with the facility of check-ins, which can be utilised for many busi-ness purposes. In most cases, a check-in generates a triplet   u,l,t   indicating thatuser  u   checked-in at location  l   associated with spatial information   x,y   at a spe-cific  time t  , which also shows that the user is temporally online. Consequently,this leads both industry and academia to consider the time dimension. Peopleon social networks communicate with each other and this interaction is recordedwith time. For example, consider social network users on the Gold Coast whoare interested in a coffee shop at which their friends have already checked-in.This group of people have planned to meet up at a certain place and time. Thecoffee shop (e.g. Merlo)can also utilise its customers profiles on Facebook toprovide location-specific advertisements to potential customers, who might alsobe interested in other items offered by the coffee shop. However, this increasesthe complexity of the social network. Moreover, due to the vast developmentof online social networks, people can create and update their profiles. A hugeamount of textual information is associated with users because they can expressthemselves easily through blogging. If a Flickr user utilises many keywords re-lated to travelling (e.g. posts many photos about trips with keywords), thesekeywords help interested users to find people with similar interests. Basically,users are more likely to search for people with whom they share similar person-alities and interests or those who share similar work and research areas. Usersare progressively geo-coded and geo-positioned on social networks and there isincreased availability of textual descriptions regarding interests, such as touristattractions and cafes.This research contributes to the existing body of knowledge as well as theindustry in the field of community search. This work focuses on the social com-munity in the environment of LBSN. Due to the variant data type of LBSN,the significance of this research can be classified into three dimensions: socialrelationships, attributes, and spatio-temporal. In terms of social matter, friendrecommendations, in which the system searches for similar users to recommendthem to each other, is one of the most important outputs of community search.Moreover, as the users of LBSN can have keywords or tags to describe them- 4 http://www.facebook.com 5 http://twitter.com 6 https://foursquare.com 7 http://www.statisticbrain.com/facebook-statistics 8 Foursquare statistics. https://foursquare.com/about/ 9 www.twitter.com  Effective Community Search Over Location-Based Social Networks 3 selves or their businesses, a self-drive tour of a set of POIs or a minimum groupof people, who share similar interests, could be achieved using an attributedcommunity.To model and search complex social graphs meaningfully, the simple graphmodel is often not adequate to capture many real-world social network datasets.As previously noticed from the examples, for most social networks, informationis not only available about social connections but also about user demographics,preferences, actions performed, and so on. Combining both the explicit spatialassociation of a place and the implicit semantics of interaction with s placeprovides a unique opportunity for in-depth understanding of both places andusers. Hence, in this research we investigate the possibilities of   spatio-attributed community search   to enrich the simple graph model. 2 Related Work Community search is a community retrieval approach that aims to find a denselypopulated query-based on-line connected community [Fang et al., 2017, Li et al., 2015]. For example,  k-core   [Seidman, 1983] was utilised in [Li et al., 2015, Sozio and Gionis, 2010]. [Sozio and Gionis, 2010] designed the first algorithm Global to retrieve the connected  k-core   that includes the vertex  q  . In detail, the problemwas formulated as  Q  , a set of query nodes or seeds against a graph  G  = ( V,E  )to retrieve a connected subgraph including  Q  . Thus, the authors suggested afunction called the goodness function  f   to measure the goodness of the subgraph.Moreover, this work [Sozio and Gionis, 2010] considered subgraph density by using two other functions: the average and minimum degree of the subgraphnodes  f  a  and  f  m , respectively. 2.1 Attributed community search An attributed community is represented by vertices associated with text orkeyword-named attributes. These attributes can effectively provide more featuressuch as ease of interpretation and personalization [Fang et al., 2017]. Recently, [Shang et al., 2017] proposed an attributed community search method, which was enhanced by [Huang et al., 2014], with a refining technique. The main idea was to reconstruct the graph based on topology-based and attribute-based similarities.The new reconstructed graph was called the TA-graph. Based on the TA-graphstructure, an index named AttrTCP-index based on TCP-index[Huang et al.,2014] was created. Thus, queries that are on the new index AttrTCP-index re-turn to communities that satisfy the queries. Moreover, [Fang et al., 2017] inves- tigated the attributed community search by combining a cohesive structure andkeyword. The data model in this study was similar to the previous one [Shanget al., 2017], specifically in keywords for which each vertex  v  is associated witha set of keywords. However, this work utilised the  k  − core  technique [Seidman, 1983] and the decomposition algorithm proposed in [Batagelj, 2003] to find a  4 I.Alaqta et al. cohesive structure called a connected  k − core  denoted by   k  −  core . More signif-icantly, the study designed an index called the Core Label tree (CL-tree), whichputs the   k  −  core  and keywords in a tree structure. Based on the  k  −  core  defi-nition, the authors identify the research problem as given  G  = ( V,E  ), a positiveinteger  k , a vertex  q   ∈  V    and a set of keywords  S   ⊆  W.  In community search,index construction plays a key role due to the effective and efficient impact onresults. Since cores can be nested[Batagelj, 2003], the CL-tree index [Fang et al., 2017] was constructed. Obviously, a   k  −  core  must contain   ( k  + 1)  −  core . Thus,a tree structure is the most suitable data structure for such  k  −  cores . 2.2 Spatial community search Spatial graphs are on-line social networks on which users can share their locationinformation, e.g. their position during check-ins. Spatial community search canperform community retrieval techniques, e.g.  k-core or k-truss   on a spatial socialnetwork. For example, given a Geo-Social Graph  G , and a query vertex  q  , the taskof spatial community search is to find a subgraph of   G . This subsection reviewsthe most considerable works in terms of a spatio-social community search, aspreviously reviewed works assume non-spatial graphs [Cui et al., 2013, 2014, Huang et al., 2014, Li et al., 2015, Sozio and Gionis, 2010]. It can be said that a recent work named  spatial-aware community   (SAC) [Fang et al., 2016] has adopted the concept of minimum degree, which basically depends on the  k − core technique. SAC is a subgraph denoted by  H   = ( V   H  ,E  H  ), which needs to satisfythe following: –  Connectivity,  G q  ∈  G  is connected and q exists. –  Structure cohesiveness  ⇒  all vertices are intensively linked in  H  . –  Spatial cohesiveness  ⇒  all vertices are almost at the same spatial location.Compared to traditional CS works, condition three is intuitively what distin-guishes SAC. So, spatial cohesiveness in SAC is defined to achieve a minimumcovering circle (MCC) with the smallest radius. The formal definition is thatgiven a set of vertices  S , the MCC of   S  is the spatial circle that contains allvertices in S with the smallest radius. SAC follows the two-step framework: (1)find a community S of vertices, based on some CS algorithm [Sozio and Gionis, 2010]; and (2) find a subset of S that satisfies both structure and spatial cohe-siveness.All reviewed methods consider social constraints. Some reinforce social querieswith extra constraints, e.g. keywords, location, and time. However, there is alack of integration of all constraints into one CS framework. Therefore, this arti-cle proposes a conceptual framework to enhance the effectiveness of communitysearch models over LBSN. The enhancement has been enforced by integratingcompatibly text-mining techniques with a community search model as demon-strated in Figure 1.  Effective Community Search Over Location-Based Social Networks 5 Fig.1.  Research Gap 3 Methodology This research has developed a hybrid approach, which aims to search for desiredquery-based social communities over LBSN. Our hybrid approach considers threedifferent dimensions,  including keywords, location, and time  , which significantlyenhance the effectiveness of social community search outputs. Therefore, theapproach has combined different methods in which each method is required toachieve its research objectives under one framework. 3.1 Problem Formulation In this section, we provide definitions that will be used throughout the paper.Also, this section provides the problem statement followed by an example toelaborate our research problem. Data Model:  We consider the location-based social network  G  = ( V,E,X  ) as anattributed graph, where  V    is a set of all users. Each edge  e ( u,v )  ∈  E   indicatesthat a friendship exists between two users.  X   denotes a matrix [ X  ] n  ×  l  where l  is the number of all possible distinct keywords  W  , which are associated withplaces  P   that have been visited by users in form of 4-tuple check-in point CK. So, CK   =  { u i ,p k ,t,W   p k | u i  ∈  V,p k  ∈  P  }  where  p k  is identified by a unique GPScoordinate and  t  is a time-stamp when a user  u i  checked-in  p k . For example, inFigure 2 there are nine users, i.e.  u 1 ,...,u 9 .  Some conform with the conditionsof inducing dense subgraphs. For instance,   u 1 ,u 2 ,u 3 ,u 4  ,  u 7 ,u 8 ,u 9   are twosubsets, which form socially dense subgraphs. Moreover, our example shows thatusers could visit places either as a group or individually, e.g.   u 1 ,u 2 ,u 3 ,u 4  checked-in at the same time  t 1  and the same place as well, which results inkeeping a dense spatio-temporal relationship. Later, we will learn how to defineour query model to retrieve communities. Based on our data model, we give thefollowing definitions followed by the query model. Query Model:  The main goal of our framework is to search the community of a location-based social graph. Our query model is maintained by several con-straints that need to be satisfied to return an Attri-Spatial Social Community.
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x