Movie and Genre Similarity using Link Analysis

Here we again measure movie genre similarity, but instead of simply counting genre co-occurrences, as in the previous post, we use link analysis. That is, we construct a bipartite graph, where the first part represents movies and the second part consists of genres, and . See the plot below for a sample from the imdb dataset. 

Each movie is connected to one or more genres. The average number of genres per movie is about 2.7. The data above represents a small portion of the total dataset. 
For this analysis below, we partition the dataset by decade, as before in the previous post. The set of movies and genres are denoted A and B, respectively Define s_A(X, Y) to be the similarity between movies, and s_B(x, y) to be the similarity between genres. We use the following equations to calculate the similarity between two movies X,Y ∈ A:

Similarly, we use the following equations to calculate the similarity between two genres x,y ∈ B:

Note that if X = Y, then s_A(X, Y) = 1. Also, if x = y, then s_B(x, y) = 1. That is, a movie X is 100% similar to itself; likewise, a genre x is perfectly similar to itself. 
C₁ and C₂ are decay constants in the range (0, 1). O(X) is the number of edges of movie X, and O_i(X) is the genre, x ∈ B, of the ith edge of X. The terms that use Y can be treated the same. I(x) is the number of edges of genre x, and I_i(x) is the movie, X ∈ A, of the ith edge of x. The terms that use y can be treated the same. 
We initialize all s_A(X, Y) and s_B(x, y) to 0 where X ≠ Y and x ≠ y; otherwise, s_A(X, Y) and s_B(x, y) are set to 1. 
All combinations of elements of A must be calculated, as must all combinations of elements of B. There are $ \binom{|A|}{2}} $  pairs of X,Y ∈ A, and \$ |B| \choose 2 \$ pairs of x,y ∈ B. The two equations above, for s_A(X, Y) and s_B(x, y), must be calculated for each pair, resulting in $ \binom{|A|}{2} + \binom{|B|}{2} $ calculations. These calculations must be repeated until the values of s_A and s_B converge. This may take several iterations. Here the criteria is that the total change over all pairs is less than 0.1.
After  s_A and s_B have been calculated
One advantage of the method above over the co-occurrence method is that we calculate movie similarity as well as genre similarity. This allows us to give movie recommendations. If we know a user likes movie X, then all we need to do is find movies similar to X and recommend them. For example, the results of the above algorithm gives that the four most similar movies to The Shawshank Redemption are:
What Becomes of the Broken Hearted?

Hidden Agenda

South Central

Some Mother's Son

This seems right. These movies definitely share some characteristics of The Shawshank Redemption. 

Another example should suffice. Here are the 4 most similar movies to The Matrix:

Dragon Inn

American Ninja V

Operation Delta Force 3: Clear Target

The Defender

A third example should further suffice things up. X = Pulp Fiction. Recommendations =

Safe House

The Rich Man's Wife

Darr

Incognito

Note: these similar movies are calculated by the decade; that is, if the query is a movie from the 1990's, the recommendations will only be movies from the 1990's. Doing all movies together takes too much time with the algorithm above.

Below is a side-by-side comparison of the results of this post and the results in Co-occurrences. Again, each column is for a decade, and the higher genres are the ones closest (most similar to) the Comedy genre.

So now we have genre-genre similarity and movie-movie similarity. In order to determine genre-movie similarity, we will employ personalized PageRank, a topic for another post.

Movie Genre Similarity using Genre Co-occurrences

This page shows a few ways of visualizing movie genre similarity. The similarity scores were obtained by iterating through an IMDB dataset of 10,000 movies from the 1950's to the 2010's, and counting the number of times each genre appeared with the other genres. For example, if a movie's genres were Action, Adventure, and Comedy, the co-occurrence counts would go up for the following pairs: (Action, Adventure), (Action, Comedy), and (Adventure, Comedy). The resulting co-occurrence count matrix is shown below. 
The color map is as follows: 1.0 is perfect similarity, and 0 is total non-similarity. 

The next three visualizations focus on individual genres. For the Comedy genre plot below, the more similar a genre, the higher the label. The plot below is not to scale. The genres are simply ordered most-to-least similar, top-to-bottom. The data is also time sliced by decade, as indicated at the bottom of the plot. Observe the changes in rank over time. 

This plot is to scale, although that scale is not shown. 

The plot below shows essentially the same thing as above, but using line plots, showing scale, and with lower similarity genres filtered out. 

There are 24 genres in total, and not enough room for them here. Feel free to request a particular genre, and I'll try to post it. 

For those interested in more detailed view, below is a plot using 1-year time slices (as opposed to the 10-year slices used above), for the Sci-Fi genre. 

The plot below, for the Mystery genre, is for 2-year time slices. Notice the rise in similarity to the Thriller genre, and the jagged wave shape of the Horror genre. Apparently, intense feelings of fear and shock, combined with puzzlement, are popular approximately once per generation. 

This analysis was made with python, specifically numpy, pandas, matplotlib. 

•