I am forwarding this, as Dan asked below.


-------- Original Message --------
Subject: Fwd: failure notice
Date: Mon, 23 Apr 2012 17:27:21 +0200
From: Dan Brickley <dan...@danbri.org>
To: castagna.li...@googlemail.com

bugger, wrong email account! care to fwd this if you want to reply?
I'll try to fix my setup but can't do it right now... --Dan

---------- Forwarded message ----------
From:  <mailer-dae...@apache.org>
Date: 23 April 2012 17:21
Subject: failure notice
To: dan...@danbri.org

Hi. This is the qmail-send program at apache.org.
I'm afraid I wasn't able to deliver your message to the following addresses.
This is a permanent error; I've given up. Sorry it didn't work out.

Sorry, only subscribers may post. If you are a subscriber, check to be
sure you are sending from your subscribed address. (#5.7.2)

--- Below this line is a copy of the message.

Return-Path: <dan...@danbri.org>
Received: (qmail 84383 invoked by uid 99); 23 Apr 2012 15:21:56 -0000
Received: from athena.apache.org (HELO athena.apache.org) (
   by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 23 Apr 2012 15:21:56 +0000
X-ASF-Spam-Status: No, hits=-0.0 required=5.0
X-Spam-Check-By: apache.org
Received-SPF: neutral (athena.apache.org: local policy)
Received: from [] (HELO mail-bk0-f47.google.com) (
   by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 23 Apr 2012 15:21:51 +0000
Received: by bkcjk7 with SMTP id jk7so2927962bkc.6
       for <giraph-user@incubator.apache.org>; Mon, 23 Apr 2012
08:21:29 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
       d=google.com; s=20120113;
MIME-Version: 1.0
Received: by with SMTP id fq11mr2451545bkc.123.1335194487870;
 Mon, 23 Apr 2012 08:21:27 -0700 (PDT)
Received: by with HTTP; Mon, 23 Apr 2012 08:21:27 -0700 (PDT)
In-Reply-To: <4f84872e.4050...@googlemail.com>
References: <4f84872e.4050...@googlemail.com>
Date: Mon, 23 Apr 2012 17:21:27 +0200
Message-ID: <caffrafoxhcruv5agqny6ugxwd_dobq2dtuogecjpnj2c_cc...@mail.gmail.com>
Subject: Re: A simple use case: shortest paths on a FOAF (i.e. Friend of a
 Friend) graph
From: Dan Brickley <dan...@danbri.org>
To: giraph-user@incubator.apache.org
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Virus-Checked: Checked by ClamAV on apache.org

Hi Paolo,

On 10 April 2012 21:17, Paolo Castagna <castagna.li...@googlemail.com> wrot=
> Hi,
> I am still learning Giraph, so, please, be patient with me and forgive my
> trivial questions.
> As a simple initial use case, I want to compute the shortest paths from a=
> source in a social graph in RDF format using the FOAF [1] vocabulary.
> This example also will hopefully inform GIRAPH-170 [2] and related issues=
, such
> as: GIRAPH-141 [3].
> Here is an example in Turtle [4] format of a tiny graph using FOAF:
> ----
> @prefix : <http://example.org/> .
> @prefix foaf: =C2=A0 <http://xmlns.com/foaf/0.1/> .
> :alice
> =C2=A0 =C2=A0a =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 foaf:Person ;
> =C2=A0 =C2=A0foaf:name =C2=A0 "Alice" ;
> =C2=A0 =C2=A0foaf:mbox =C2=A0 <mailto:al...@example.org> ;
> =C2=A0 =C2=A0foaf:knows =C2=A0:bob ;
> =C2=A0 =C2=A0foaf:knows =C2=A0:charlie ;
> =C2=A0 =C2=A0foaf:knows =C2=A0:snoopy ;
> =C2=A0 =C2=A0.
> :bob
> =C2=A0 =C2=A0foaf:name =C2=A0 "Bob" ;
> =C2=A0 =C2=A0foaf:knows =C2=A0:charlie ;
> =C2=A0 =C2=A0.
> :charlie
> =C2=A0 =C2=A0foaf:name =C2=A0 "Charlie" ;
> =C2=A0 =C2=A0foaf:knows =C2=A0:alice ;
> =C2=A0 =C2=A0.
> ----
> This is nice, human friendly (RDF without angle brackets!), but not easil=
> splittable to be processed with MapReduce (or Giraph).
> Here is the same graph in N-Triples [5] format:
> ----
> <http://example.org/alice> <http://www.w3.org/1999/02/22-rdf-syntax-ns#ty=
> <http://xmlns.com/foaf/0.1/Person> .
> <http://example.org/alice> <http://xmlns.com/foaf/0.1/name> "Alice" .
> <http://example.org/alice> <http://xmlns.com/foaf/0.1/mbox>
> <mailto:al...@example.org> .
> <http://example.org/alice> <http://xmlns.com/foaf/0.1/knows>
> <http://example.org/bob> .
> <http://example.org/alice> <http://xmlns.com/foaf/0.1/knows>
> <http://example.org/charlie> .
> <http://example.org/alice> <http://xmlns.com/foaf/0.1/knows>
> <http://example.org/snoopy> .
> <http://example.org/charlie> <http://xmlns.com/foaf/0.1/name> "Charlie" .
> <http://example.org/charlie> <http://xmlns.com/foaf/0.1/knows>
> <http://example.org/alice> .
> <http://example.org/bob> <http://xmlns.com/foaf/0.1/name> "Bob" .
> <http://example.org/bob> <http://xmlns.com/foaf/0.1/knows>
> <http://example.org/charlie> .
> ----
> This is more verbose and ugly, but splittable.
> The graph I am interested in is the graph represented by foaf:knows
> relationships/links between people (please, note --knows--> relationship =
> has a direction, this isn't symmetric as in centralized social networking
> websites such as Facebook or LinkedIn. Alice can claim to know Bob, witho=
ut Bob
> knowing it and/or it might even be a false claim):
> alice --knows--> bob
> alice --knows--> charlie
> alice --knows--> snoopy
> bob --knows--> charlie
> charlie --knows--> alice

I meant to comment on this detail, but without unsettling the great
work your're doing here.

The notion of 'symmetric' in this case is very slippery, since there
are some related ideas in the mix.

1. does 'X knows Y' imply (formally or otherwise) 'Y knows X'.

On this point, FOAF is borderline (by our messy design:). The text in
http://xmlns.com/foaf/0.1/#term_knows says "A person known by this
person (indicating some level of reciprocated interaction between the
parties)."  So the commonsense reading is that it rarely makes sense
to assert that X knows Y, without also accepting the truth of Y knows
X. However there are of course cornercases, e.g. senility, or being
dead, etc. So we didn't take the opportunity to assert formally in the
schema that it is an owl:SymmetricProperty.

2. does X's FOAF file asserting that X knows Y, require Y's FOAF file
to assert that Y knows X? (or several variations on this...)

This is where we get into provenance issues, keeping track of
source/evidence and claim attribution. Alice might say she knows Bob,
and also Charlie; yet Bob might know Alice and not say so. Charlie
might say he knows Alice. Dave (who Alice does know but doesn't
mention) says he knows Alice, as does Eve (who Alice has never heard
of), etc.

That stuff gets messy quickly. It captures a certain level more
real-world realism but I think has no place in these preliminary
explorations. So it is better for now I think to assume that the same
large graph structure is "in the same voice", rather than having one
voice (asserting party) per node.

Hope this makes sense!

So, to recap:

> The graph I am interested in is the graph represented by foaf:knows
> relationships/links between people (please, note --knows--> relationship =
> has a direction, this isn't symmetric as in centralized social networking
> websites such as Facebook or LinkedIn. Alice can claim to know Bob, witho=
ut Bob
> knowing it and/or it might even be a false claim)

... yes, this relationship type "has a direction" (even if it is
typically reciprocated, in reality if not in the dataset). Other
similar RDF relationships like membership in a group, or authorship of
a paper, also "have direction". For those relationship types that go
from one class of thing (e.g. Document) to another (e.g. Person) the
direction can be left a bit more implicit, but in both cases it is
important and carries meaning.  There is an extra layer of richness we
can add if each assertion in the graph (regardless of it's 'direction'
in this earlier sense) has an attribution to an asserting party.
Consider a relationship type like "creator" linking a Document to an
Agent. Consider its approximate inverse, "made" that links e.g. a
Person to a Document. Now Charlie might say that "Alice made
document362". Dave might say that "document 362 has a creator Alice".
Our schema might say that either of these statements implies the
other. But we shouldn't mix talk about the directedness of "made" (or
"author") with the notion of who is making those claims.

Slippery stuff, so +1 on starting with the most basic of test cases
and getting the loading HOWTO done before worrying too much about data
provenance etc.

(On 'Facebook', 'friend with' is symmetric because they won't believe
A or B without asking both A or B to agree to the same claim. Twitter
follows is a bit different, etc.)



Reply via email to