Social Network (SN) data has become ubiquitous, demanding advanced and exible means to represent, transform and query such data. In addition to the intrinsic challenges of querying graph data is the requirement that networks be restructured, and thus that new values be created. To address these, we introduce a dedicated data model and query language, SNQL, founded on previous research on graph databases and on the experience of SN researchers. Technically, it is based in GraphLog and second-order tuple generating dependencies, allowing expressiveness for graph querying and node creation as required by SN, while keeping the complexity of query evaluation in NLOGSPACE.
The widespread embracing of social networking services|such as Facebook, MySpace and LinkedIn|as the indispensable tools to manage people's digital and physical lives has resulted in rapidly growing amounts of social activity data. Furthermore, the social information represented by many sites usually includes not only people but a great variety of objects (usually referred to generically as actors in the social networking literature) and relations: photographs (Flickr), other sites (del.icio.us), places (Yahoo! Travel), goods (Amazon), and so on. This diversity produces complex social networks (SN) which require managing, querying and transforming.
In the context of these new applications, users have access to an
increasing amount of SN data, and consequently the need arises for them to manage
and build their own networks based on relevant \pieces" of the huge networks
available. For example, it is common to nd applicable online information about
published research linked with departmental and local scienti c networks. This
calls for more advanced and exible means to query and transform SN data.
Along the same lines, scienti c experimentation with social network analysis
(SNA) tools (e.g. Pajek [
A further requirement is that SN data representation needs to be exible enough to incorporate on-the- y attributes (e.g. for data curation). In addition, data is used and seen from diverse points of view by di erent users. Hence classical modeling in terms of a xed set of entities, attributes and relationships does not work well. For example, in SNA it is common for attributes to become actors, for aggregated data of actors to become attributes, and for relations to have arity greater than two.
Example 1. Consider a SN of friendship relations among people, including which other person, if any, introduced them; this implies having relations of variable arity (solved by representing relations as nodes). People are described by the attributes `name' and `city' (see Fig. 1(a)). The study of the relevance of city of residence to friendship might require promoting cities to actors and linking people and cities with a new type of relation, e.g. `lives-in' (see Fig. 1(b)). Another type of transformation would be to group people by city of residence, thus de ning a network of cities, where relations summarize friendships among residents of cities. Additionally, one might like to describe in the network the population (person count) of each city, and label the relations between them with the number of friendship-relations between people (see Fig. 1(c)). tu
The requirements suggested by Example 1 together with the integration of diverse types of information as described above call for a simple and exible model of data for SN. Furthermore, due to the growing volume of SN data, any transformation and query language for SN should be scalable. This implies that a transformation and query language should conform, from a theoretical perspective, to low complexity bounds, and, because of practical concerns, be simple and modular while being su ciently expressive.
Several of these challenges have been already voiced. Fifteen years ago
Freeman de ned the maximal structure experiment that extended the basic network
representation to include attributes as well as to accommodate changes over
time [
To date, the above challenges have been addressed with ad-hoc approaches,
and to the best of our knowledge there is no generic data management
solution in spite of the wide agreement on the urgent necessity of addressing this
problem [
The three most comprehensive proposals on the challenges presented above
are BiQL, SocialScope, and SoQL. SocialScope [
Our transformation and query language, named SNQL, is inspired by two
earlier languages: GraphLog [
GraphLog was a seminal query language for graph data, designed to be expressive while at the same time having low computational complexity. Apart from standard features, it includes aggregation and transitive closure making it suitable for many SN queries. However, GraphLog does not provide functionality to create new objects/actors, a crucial requirement for SN.
Example 2. Consider again the SN from Example 1. The following SNQL query produces the network depicted in Fig. 1(b) from that in Fig. 1(a) by promoting the `city' attribute to a new type of actor (city ) and producing a new type of relation (lives-in) to associate people with cities.
CONSTRUCT CP IF R2 = f(A1, A2) AND A2 = g(L1)
WHERE EP
FROM FriendshipNetwork Patterns EP and CP, depicted in Fig. 2, denote an extraction pattern and a construction pattern, respectively. FriendshipNetwork is the SN shown in Fig. 1(a).
Note that in the result, cities become hubs that connect all people living in each of them, and that the new actors require creation of new ids from the data:
Extraction Pattern: EP L1 city
A1 name
P1 person the oids of cities are produced by applying a function g to the literal values bound to variable L1. Similarly, new relation identi ers for the `lives-in' relation are created using f , one for each (person,city) pair matched by (A1,A2). tu
Creation of values was addressed by database query languages such as IQL [
Our contributions are as follows: 1. A data structure capable of representing the informational richness and malleability of social networks. 2. A transformation and query language satisfying the data management requirements of social networks with good properties: adequate expressiveness, and accessible to social networks eld practitioners. 3. A query language that includes object creation but maintains low complexity. 4. A corresponding evaluation algorithm whose complexity scales adequately.
The outline of the rest of the paper is as follows. Section 2 brie y presents the requirements and SNA use cases. Section 3 de nes the syntax (via examples) and semantics of SNQL. Section 4 presents results on the expressiveness and complexity of SNQL. We included an Appendix with complete syntax and extended related work. 2
To identify the general requirements and operations needed for SNQL, we
collected use cases and archetypical operations from standard SNA literature [
Use Case Description Required Query Features 1. Selecting Select a subnetwork of actors and relations that Pattern matchGroups satisfy conditions on their attribute values and/or ing, ltering by participation in certain relations. attributes values. 2. Pro- From an actor A1 and one of its attributes (att; v) Pattern matching, moting produce a new actor A2 = f (v) and a new relation creation of new obAttributes R = g(A1; v) (f and g functions): all actors with jects, pattern proto Actors value v for att will be connected to A2. duction. 3. Identify- For each characteristic brokerage pattern found, Pattern matching, ing Brokers label the broker in the output accordingly. Some negation, pattern patterns require certain relations do not exist. production. 4. Counting Select all relations of a given type, group by par- Pattern matching, Binary Rela- ticipant actors, count. Produce only one relation aggregation, pattions per group with the new attribute count. tern production. 5. Ego- Select an actor along with all its direct neighbors, Pattern matching, network and the relations between them. induced subgraphs. selection 6. neighborhood The natural and traditional choice for representing social networks is to use graphs where actors are nodes and relations are edges. However, doing so limits the representation power to that of binary relations and forbids attributes on relations. Thus, our logical data structure, the social networks data model (SNDM), is a graph where actors, relations and attributes are all modeled as nodes, and edges associate attributes with the actors or relations they describe, and actors with the relations in which they participate. This structure is implemented using three sets of triples: { A typing set N. Each triple (oid; [isajisr]; family ) 2 N indicates that the actor (isa) or relation (isr) oid belongs to (is of type) family. { A set R indicating roles. Each triple (a oid; role; r oid) 2 R indicates that the actor a oid participates with role in the relation r oid. { A set M describing attributes. Each triple(oid; pred; v) 2 M indicates that the actor or relation oid has the attribute pred with value v. 2.2
Social networks operations can be divided into two groups: data management operations that return a social network, and measure operations that return values or sets of values, such as centrality. Today there are various tools that deal with measure operations (e.g. Pajek, R, and UCINET) and clearly belong more to the SNA tools eld than to the data management one.
SNQL focuses on the rst type, data management operations, which produce
networks from networks. Through the use of aggregate functions, we assume
that node, group and network measures are available to the language but do not
need to be expressible in the language itself. Brandes [
Each SNQL query must be able to lter and/or transform a given SN into a new SN. Filter queries are used to reduce the size of a SN and to focus on relevant groups. Transformations produce a new SN where some implicit structural element has been made explicit. 3
The design of SNQL addresses the following issues: to be expressive enough, and keep the evaluation cost under practical bounds. The challenge was to identify a few generic operations to cover the required expressiveness, and to be closed, that is, to be able to construct (and transform) social networks into social networks. 3.1
The language should be friendly enough for both the lay-user and the
programmer. For the former, a visual language close to the SN graphical representation
is ideal: in the simpler cases, one extraction pattern and one construction
pattern cover many use cases; in the general case, the extraction pattern should
resemble the DAG of query graphs that exists in GraphLog [
At the abstract level, and for the purpose of formally studying and analyzing
its semantics and complexity, we use a translation to a more formal
representation, based on Datalog/GraphLog [
An SNQL construct query Q follows the standard SELECTjCONSTRUCT { WHERE { FROM structure of languages like SQL and SPARQL. It receives as input social networks (the FROM clause), extracts information using patterns (the WHERE clause), and outputs a new social network, possibly with new values, using the CONSTRUCT clause. For space reasons, we present the syntax of SNQL by example2, using the SN of friendship relations among people presented in Example 1 (see Fig. 1). 2 The complete syntax can be found in the tech report TR/DCC-2011-5 at http://www.dcc.uchile.cl/reportes city A3 person
Contruction Pattern 1: CP1 Contruction Pattern 2: CP2 A4 name L1 number city inhabitants L4 A5city friend Rfr2iendshipfriend between cities
A6 city
Example 3. (Promoting Attributes to Actors) Recall the query from Example 2, where the patterns EP and CP were depicted in Fig. 2. Expanding the patterns as lists of triples, the query is as follows: CONSTRUCT {(A1, isa, person), (A2, isa, city), (R1, isr, friendship), (R2, isr, lives-in), (A1, inhabitant, R2), (A1, P1, R1), (A1, name, L2), (A2, place, R2), (A2, name, L1)}
IF R2=f(A1, A2) AND A2=g(L1) WHERE {(A1, isa, person), (R1, isr, friendship),
(A1, city, L1), (A1, P1, R1), (A1, name, L2)}
FROM FriendshipNetwork Example 4. (Grouping and Aggregation) The following SNQL query produces the network depicted in Fig. 1(c) from that in Fig. 1(a), grouping people by city and counting friendship relations between cities.
CONSTRUCT CP1 IF A4 = f(L1) AS SN1
WHERE AGG({L1}, COUNT AS L4, EP1)
FROM FriendshipNetwork UNION CONSTRUCT CP2 IF A5 = f(L2) AND A6 = f(L3) AND R2 = g(A5, A6) AS SN2 WHERE AGG({L2,L3}, COUNT AS L5, EP2 FILTER (L2 != L3))
FROM FriendshipNetwork Patterns EP1, EP2, CP1, and CP2 are depicted in Fig. 3. Note that each new group (actor) requires a new oid functionally produced from the value of attribute `city'. Also the number of inhabitants bound to L4, and the number of friendship-between-cities bound to L5, must be computed with the aggregate function COUNT. The rst argument of AGG is the set of grouping variables, the second is the aggregation function required, and the third is an extraction pattern. The results of the two construct queries are combined using UNION to produce the desired result. tu Example 5. (Transitive Closure) The following SNQL query (whose patterns are shown in Fig. 4) produces the network comprising an actor that meets a given criterion (his name is `John'), along with all other actors that can be reached transitively by matching the given pattern (of friendship relations). Additionally all induced relations between pairs of reachable actors are included in the result. Extraction Pattern 1: EP1 (TC)
L1
Extraction Pattern 2: EP2
L3
Extraction Pattern 3: EP3 (TC)
L1
Contruction Pattern 1: CP1
L3 name A1 friend person TC returns the transitive closure of the binary relation formed by all instantiations of the variables appearing as its rst and second arguments when matching the extraction pattern of its third argument. A starting condition is speci ed after WITH. Hence variables A2 and A5 are bound to the people reachable from John through transitive friendship relations. Pattern EP2, along with the FILTER conditions above, is then used to match all the induced friendship relations between distinct pairs of people reachable from `John' (along with `John' himself). tu 3.2
An SNQL query Q of the form CONSTRUCT <T> WHERE <PATT> FROM <S> transforms social networks into social networks.
The formal semantics can be expressed in standard formalisms (Datalog and tuple-generating dependencies) as follows. Let D be a social network, Q an SNQL query, and Q(D) the result of applying Q to D. For set of variables X, let x be the tuple comprising all variables in X.
An extraction pattern is recursively decomposed and simulated by a Datalog program as follows. Let PATT be the pattern to be simulated by predicate p and assume that patterns PATT1 and PATT2 are simulated by p1 and p2, respectively. Let z, x and y contain the projected variables of PATT, PATT1 and PATT2, respectively. The translation, based on the structure of PATT, is shown in Fig. 5.
The predicate p obtained from pattern PATT in the previous translation, is now used to produce the query result. Here the list of triples of the CONSTRUCT clause along with the corresponding lists of equalities play a central role. The equalities are of two types. One type de nes each variable: vi = termi, 1 i k; the other is of the form termi = terml, where each term may contain variables (from p), constants and functions.
For a given CONSTRUCT trList IF eqList the construction process takes the result of the extraction process, the p(z) predicate, plus the list of equalities eqList translated as ^jeqj to produce the following rule: (1) (2) tu
Finally, the resulting social network SN is the set of instantiations of each triple t in the list of triples trList in the CONSTRUCT using the values in the construct predicate:
SN = [ nt(u1; u2; u3) : 9(::u1::u2::u3::) 2 construct and t in trList o Example 6. Consider the SNQL query Q of Example 4 that involved grouping and aggregation. The translation of Q to Datalog is shown in Figure 6. 4
The main goal of this paper was to introduce a su ciently exible data model and expressive query language that meets the data manipulation requirements of social networks. In this section we state|without proof due to space constraints3|results that show the good behaviour of the language regarding complexity and expressive power.
SNQL is composed of two modules: one for extraction of information and one for construction of a new network. In the design, consideration has been given to providing the maximum expressiveness possible while keeping the complexity of processing within reasonable bounds. First, for extraction, we considered GraphLog (possibly with summarization functions), which is designed to
http://www.dcc.uchile.cl/reportes the tech report
TR/DCC-2011-5 at output-n(A4,isa,city) :- construct1(A4,L1,L4) output-m(A4,name,L1) :- construct1(A4,L1,L4) output-m(A4,inhabitants,L4) :- construct1(A4,L1,L4) output-n(A5,isa,city) :- construct2(A5,R2,A6,L5) output-n(R2,isr,friendship-between-cities) :- construct2(A5,R2,A6,L5) output-n(A6,isa,city) :- construct2(A5,R2,A6,L5) output-r(A5 friend,R2) :- construct2(A5,R2,A6,L5) output-r(A6,friend,R2) :- construct2(A5,R2,A6,L5) output-m(R2,number,L5) :- construct2(A5,R2,A6,L5) construct1(A4,L1,L4) :- ag1(L1,N), A4=f(L1), L4=N ag1(L1,count(A1)) :- ep1(A1,L1) ep1(A1,L1) :- n(A1,isa,person), m(A1,city,L1) construct2(A5,R2,A6,L5) :- ag2(L2,L3,M), A5=f(L2), A6=f(L3),
R2=g(A5,A6), L5=M
ag2(L2,L3,count(A2,R1,A3)) :- ep2(A2,A3,R1,L2,L3)
ep2(A2,A3,R1,L2,L3) :- n(A2,isa, person), n(R1,isr,friendship),
n(A3,isa,person), r(A2,friend,R1),
r(A3,friend,R1), m(A2,city,L2),
m(A3,city,L3), L2 != L3
be as expressive as possible while staying within the LOGSPACE complexity
bound [
It is therefore not surprising that SNQL covers all use cases of reasonable complexity that we identi ed in current SN practice. (There are still some queries which are not covered by SNQL, but it can be proved that they fall outside a reasonably e cient complexity bound. A typical example is cohesive subgroups such as k-cores.) Formally stated, this result can be presented as follows: Claim. SNQL can express all use cases identi ed in SN practice that fall in the NLOGSPACE complexity bound.
A formal proof of this claim relies on the list of use cases in current practice. The column \Required Query Features" of Table 1 collects the features needed for the classical use cases from the SN community. All of them, except induced subgraph, are incorporated directly in the language. For the induced subgraph, Example 5 gives the idea how this is done.
As for the expressive power as compared to classical databases languages, we can prove the following two results: Theorem 1. SNQL extraction has the same expressive power as GraphLog. (a) For an expression
CONSTRUCT trList1 IF eqList1; ... trListn IF eqListn; translated in the form of eq. (3), de ne n clauses: auxj(xj) p(x)^Vk eqk; j = 1; : : : ; n. (b) For each clause trListj IF eqListj; and each triple (x,y,z) in trListj, dene a rule t(x; y; z) auxj(xj). (c) Add the clauses generated by (a) and (b) to the original Datalog program generated from the extraction pattern (see Fig. 5). (d) Obtain the values of the triples to be generated by running the new program.
Theorem 2. SNQL construction can be speci ed by one SOtgd of the form: 9f1 : : : fm(8x1( 1 ! 1) ^ : : : ^ 8xn( n ! n)); where each ( i ! i) has the form: (p(x) ^ ^ eqk) ! (t1 ^ : : : ^ tr); k (3) where p(x) and eqk follow the notation of (1) and (2), that is, predicate p(x) is the result of the processing of the extraction pattern, and tj and eqk are predicates resulting from the translation of the triples and equalities in the CONSTRUCT clause, and each tuple xi includes all variables in p and in the eqk's.
A naive implementation of the semantics presented in Fig. 5 would materialize intermediate results. This can be avoided by using the algorithm in Fig. 7. Lemma 1. The Evaluation Algorithm is correct|it preserves SNQL semantics.
It is possible to show that the above evaluation computes queries e ciently
from a database perspective. As is customary when studying the complexity
of the evaluation problem for a query language [
QUESTION : Is t 2 [[Q]]D? Theorem 3. The complexity of Evaluation is in NLOGSPACE. 5
Based on social network practice, we have presented the design of a data model and query language for SN. Of particular novelty, is the ability of our language to transform one network into another, in the process creating new actors and new attributes based on aggregation, features crucial for social network researchers.
We presented the syntax, semantics and complexity analysis. The language is based on classical database results to obtain a good balance between expressiveness and complexity. Presenting both a graphical and SQL-like syntax, we designed it to have the most encompassing expressiveness while staying tractable. In fact, we show that it includes all tractable operations found in our survey of SN data management practice, and we prove that the cost of transforming networks can be done e ciently from a computational point of view. Acknowledgements. C. Gutierrez thanks FONDECYT 1110287. P. T. Wood visited the U. of Chile funded by a Royal Society International Joint Project.