Standard Recommendation

[Eric Gold]

Suppose we have the graph:

11 12 1
11 13 1
12 13 1
13 12 1

What should the standard recommendation for node 11 be? Node 11 is connected to both of the other nodes already, so it seems that there can be no valuable recommendation to give.

[Eric Gold]

Also, what if we have a graph:

11 13 1
13 11 1

Can a recommendation for node 11 be node 11? Notice that node 11 does not have a connection to itself, so it is possible for this to be a valid recommendation. Node 11 is in its own 2-neighborhood, but it seems a bit odd to recommend yourself.

In light of this new idea, I'd like to clarify my first question and change the graph to:

11 12 1
11 13 1
12 13 1
13 12 1

11 11 1

Now it is absolutely clear that node 11 is connected to everything else in the graph, and so there are no more recommendations to give to it.

[James Feher]

I've read the other posts about this method, but they seem
contradictory to the pdf. From what I've read, the neighbors of a
vertex v are both those that point to and away from that vertex.
However, the pdf says that the algorithm for standardrecommendation is
only concerned with the directed path to v, not any path between v and
a node two edges away.

These are the lines that I am referencing from the pdf:
"The sum of all paths to v is greater than that of any other vertex
which also meets the above requirements.3"
"3Notice that we specify paths to v. The input graph is directed."

Please clarify if possible, thanks!

[Joseph Manganelli]

Intuitively, it does not make sense to recommend ONLY friends who talk
to your friends who talk to you. Why not recommend friends who talk to
OR are talked to by your friends (who are talked to by you OR you talk
to)? In other words treat the graph as undirected (in standard
recommendation).

If anything, it should be to opposite, where "The sum of all paths
FROM v is greater than..." because, just because someone talks to you
doesn't mean they are your friend.

Intuitively, the "1-Neighbor" who only talks to you could be a
spammer, and the "2-Neighbor" who only talks to that same "1-Neighbor"
could be a spammer on a spammer. I definitely don't want that vertex
as a friend :P

[Joseph Manganelli]

FYI - In my first paragraph above, I was merely asserting my opinion.
I am a student, and not entirely sure if my statements above are
correct.

[Robert Escriva]

We've released a clarification via CMS. If it does not answer your question,
please let me know.

-Robert

[Gary Peng]

I'm a little confused. The clarification email says both edges should
be "directed away fro the person to whom you are making a
recommendation" for one method of making of recommendation, but the
pdf says to look at paths going to the vertex (v) for which we are
making a recommendation. Which one should we follow if we are not
ignoring directionality?

[Gregory Hill]

What should our algorithm do if no two neighbors exist? I wanted to
throw an exception but to do that I would have to add a throws
declaration to the standardRecommendation in the Graph class. Is that
okay?

On May 3, 6:14 am, Robert Escriva <escr...@cs.cornell.edu> wrote:

[Robert Escriva]

If it is not possible to make a recommendation to a user, recommend that
the user be friends with themselves. That is, if there is no suitable
vertex to recommend, return the input.

-Robert

[James Feher]

@Gary From my understanding, it seems as though as long as you don't
follow the pdf for this part of the assignment you're okay >.<

@Gregory There is another post about this where Robert says "If it is

not possible to make a recommendation to a user, recommend that
the user be friends with themselves. That is, if there is no suitable
vertex to recommend, return the input."

[Brady Jacobs]

2 questions:  1) when you say we can either treat it as directed or undirected, can we do it differently for our Adjacency List and Adjacency Matrix, or should we keep the behavior the same for both implementations?

2) when treating it as a directed graph, if a vertex has an edge pointing to the vertex you're making a recommendation for (v) but there is no edge point from v to it, is that still a valid recommendation?  It is technically not adjacent to v, but v is adjacent to it.  How should we treat that?

[Robert Escriva]

On Tue, May 03, 2011 at 12:25:19PM -0400, Gary Peng wrote:
> I'm a little confused. The clarification email says both edges should
> be "directed away fro the person to whom you are making a
> recommendation" for one method of making of recommendation, but the
> pdf says to look at paths going to the vertex (v) for which we are
> making a recommendation. Which one should we follow if we are not
> ignoring directionality?

S->v->T or S<-v<-T are both acceptable.

-Robert

[Robert Escriva]

On Tue, May 03, 2011 at 02:47:40PM -0400, Brady Jacobs wrote:
> 2 questions: 1) when you say we can either treat it as directed or
> undirected, can we do it differently for our Adjacency List and
> Adjacency Matrix, or should we keep the behavior the same for both
> implementations?

It should be consistent between implementations.

> 2) when treating it as a directed graph, if a vertex has an edge
> pointing to the vertex you're making a recommendation for (v) but
> there is no edge point from v to it, is that still a valid
> recommendation? It is technically not adjacent to v, but v is
> adjacent to it. How should we treat that?

It is in the 1-neighborhood of v, and so it cannot be recommended.

-Robert

[Ying Qin]

so , in directed case, when we try to determine which vertex is in 1-
neighborhood, we should still think in terms of an undirected graph,
that is, vertices with incoming edges from v and vertices with
outgoing edges should all be in an undirected graph?
But when we consider the 2-neighborhood, we only consider the
vertices with incoming edges form v's 1-neighbors?

[Robert Escriva]

"Adjacent" is defined the same for both the one neighborhood.

That is, the 1-neighborhood is adjacent to a vertex. The 2-neighborhood
is the union of all 1-neighborhoods of vertices in the 1-neighborhood,
and the 1-neighborhood itself.

-Robert