No doubt working with huge data volumes is hard, but to move a mountain, you have to deal with a lot of small stones. But why strain yourself? Using Mapreduce and Spark you tackle the issue partially, thus leaving some space for high-level tools. Stop struggling to make your big data workflow productive and efficient, make use of the tools we are offering you. This course will teach you how to: - Warehouse your data efficiently using Hive, Spark SQL and Spark DataFframes. - Work with large graphs, such as social graphs or networks. - Optimize your Spark applications for maximum performance. Precisely, you will master your knowledge in: - Writing and executing Hive & Spark SQL queries; - Reasoning how the queries are translated into actual execution primitives (be it MapReduce jobs or Spark transformations); - Organizing your data in Hive to optimize disk space usage and execution times; - Constructing Spark DataFrames and using them to write ad-hoc analytical jobs easily; - Processing large graphs with Spark GraphFrames; - Debugging, profiling and optimizing Spark application performance. Still in doubt? Check this out. Become a data ninja by taking this course! Special thanks to: - Prof. Mikhail Roytberg, APT dept., MIPT, who was the initial reviewer of the project, the supervisor and mentor of half of the BigData team. He was the one, who helped to get this show on the road. - Oleg Sukhoroslov (PhD, Senior Researcher at IITP RAS), who has been teaching MapReduce, Hadoop and friends since 2008. Now he is leading the infrastructure team. - Oleg Ivchenko (PhD student APT dept., MIPT), Pavel Akhtyamov (MSc. student at APT dept., MIPT) and Vladimir Kuznetsov (Assistant at P.G. Demidov Yaroslavl State University), superbrains who have developed and now maintain the infrastructure used for practical assignments in this course. - Asya Roitberg, Eugene Baulin, Marina Sudarikova. These people never sleep to babysit this course day and night, to make your learning experience productive, smooth and exciting.
Counting common friends. Part II
Loading...
來自 Yandex 的課程
Big Data Analysis: Hive, Spark SQL, DataFrames and GraphFrames
47 個評分
從本節課中
Graph Analysis from Big Data Perspective
與講師見面
Natalia Pritykovskaya
Pavel KlemenkovChief Data Scientist
NVIDIA
Pavel MezentsevSenior Data Scientist
PulsePoint inc
Alexey A. DralHead of Big Data and Machine Learning
Algorithms and Programming Technologies dept. MIPT
But, you have two more ways to represent graphs in memory,
an Edge list and Adjacency lists.
Let's try them one by one,
start it with an Edge list.
Let's take a mini social graph as an example,
it's Edge list will look like,
people, you can see in the slide right now.
Explanation is as follows: User one has edges,<1, 2>, <1,
3>, and <1, 4>,
which reflects that user one has three friends,
two, three, and four.
We know user two, is friends with one, three, and five.
So, we should add edges,
<2,1>, <2,3> and <2,5> to our Edge list.
But, in undirected graph,
the edge <2,1>, shows us the same as edge <1, 2>.
So by adding it,
we will duplicate the information that user one and user two are friends.
So we don't add edge <2,1> because edge <1, 2> already exists.
User three has more friends than users one and two.
One, two, five, four, six, and seven.
Reverse copies of edges <3,1> and <3,2> already exist in our edge list.
So we don't add them,
but we should add edges <3,4>, <3,5>, <3,6> and <3,7>.
User four has just two friends, one and three,
they already have, reversed copies for both these edges in our list.
If you look carefully,
we will see that for the rest of users,
it has 5, 6, and 7,
they already have all possible or both copies for their edges.
each edge. User five has two friends,
two and three these are reversed copies.
<2,5> and <3, 5> added already to edge list.
User six, as well as seven has only one friend, user three.
reversed copies, <3,6>, and <3,7> are also added.
Now, let's count the amount of mutual friends for each pair of users using the Edge list.
Let's use the Spark data frame API to represent our Edge list.
Each edge will be a separate row of dataframe.
First element of each pair will go to column A,
and second, will go to column B.
If you look carefully,
you will see that vertices A and B are sorted in a scaling order.
It's important to remember this.
Remember our final goal,
for each user, we want to know,
how many mutual friends he or she has this all other users.
We want to know how many mutual friends,
user one has this all other users,
user two has this all other users and so on.
Thus, for user one,
will find the full result of computation.
This user two, he has only one mutual friend, user three.
This user three, he has two mutual friends, users two and four.
This user four, he has only one mutual friend, user three.
This user five, he has two mutual friends,
users two and three.
This user six, he has only one mutual friend, user three.
And this user seven,
he has one mutual friend, again, user three.
We will see a combinatorial explosion.
The amount of people,
this whom user one,
has at least one mutual friend is much bigger than
the amount of people user one knows directly.
So, we need to write our code in an effective way.
How can we receive the desirable results from an Edge list?
Was it pairs of vertices?
Let's call them A and C,
we will count the amount of intermittent vertices,
people who shared connections with both A and C. Let's
call them B. Dataframe discount's A and B,
we will name abDF.
Let's duplicate it first.
Second, Let's rename the column A as column B,
and column B as column C, into duplicated dataframe.
Finally, let's give this copy dataframes a name, bcDF.
So, now to find the structural pattern,
ABC to vertices A and C connected through a third
vertex B. we should in adjoin abDF to bcDF,
using the condition that abDF's column B is equal to bcDF's column B.
It's time to show you the code.
Here, we are importing all necessary libraries.
Here, we are creating the edge list for our graph.
Here, we are creating a schema for our dataframe,
namely columns A and B.
Here, we are creating the abDF dataframe.
In these two rows,
we are creating a duplicate of abDF or name in
column A to column B and column B to column C. Here,
you can see two newly born dataframes, abDF and bcDF.
Aren't they cute?
After in adjoin abDF to bcDF,
using the conditions that abDF's column B is equal to bcDF's column B,
we will receive the abcDF data frame.
This column's AC as a duplicated B,
one from abDF and second from bcDF.
Then, we can throw away the friend in the middle, column B,
because for each pair of users,
we need only the amount of their mutual friends,
and we don't need the IDs of their mutual friends.
Now, let's group our data on columns A and C,
and count the amount of times we receive each pair of users.
Finally, let's filter from the result only the rows where column A is equal to one.
We will get the next result, but wait.
Why it is that user one doesn't have any mutual friends with
user two and have just one mutual friend who's user three?
Maybe he's just too picky to make friends randomly. I don't think so.
The answer is, for each pair of vertices,
they have just the one edge.
For example, they have an edge two,
three but we don't have as symmetrical edge three, two.
After joining abDF to bcDF using
the condition that abDF column B is equal to bcDF column B,
they will not receive a row,
one, three, three, two.
That's why in the final result,
we don't receive row one, two, one.
We'll add in a symmetric copy for each edge,
fix our problem with the missing one mutual friend for the pair of vertices, one, three.
Let's check. For each edge in abDF dataframe via agent its reversed copying,
duplicate the new doubled abDF again,
renames the column AB to BC,
give a new copy name bcDF,
and perform and in a join again.
And let's take a look at this intermediate result.
For user one, we now have this.
Looks promising.
We have row one, two, two, three.
So after throwing the friend in the middle two,
we will receive the missing result that one and three have a mutual friends.
Let's finish the computation.
In the new abcDF,
let's throw away the friend in the middle,
will becomes, group all data by columns A and C,
count the amount of times we receive each pair of users,
and finally, let's filter only the rows where column A is equal to one.
We will get.
Hooray. Now, we can see that the result is correct,
and we have side effect.
We know the user one has three mutual friends.
This is user one, which is actually true because
user one and user one is the same person.
This side effect can be easily filtered in the last step of our algorithm.
In summary, we count the amount of mutual friends in five steps.
First, for each edge of abDF,
add it's reversed copy.
Create a copy of abDF and rename columns bcDF.
Join abDF to bcDF using the condition abDF column B is equal to bcDF column B.
Throw out friend in the middle B,
for each pair of vertices,
count the number of occurrences,
filter the pairs consisting of identical vertices.
What are the bottleneck of this calculation?
First of all, we double the data on our first step.
Second, we shuffle our data twice,
once on step two,
and once on step four.
Letters very expensive in terms of sending data through a network.
