0% found this document useful (0 votes)
12 views219 pages

05 Module5 RealtimeBigDataModels

The document discusses real-time big data models, emphasizing the importance of processing data instantaneously for applications like financial trading and healthcare monitoring. It outlines the architecture of a real-time big data model, including components such as data ingestion, storage, processing, analytics, and visualization. Additionally, it explores the relevance of the PageRank algorithm in real-time contexts, highlighting its applications in personalized recommendations, fraud detection, and social media analytics.

Uploaded by

Gaming Ankur
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
12 views219 pages

05 Module5 RealtimeBigDataModels

The document discusses real-time big data models, emphasizing the importance of processing data instantaneously for applications like financial trading and healthcare monitoring. It outlines the architecture of a real-time big data model, including components such as data ingestion, storage, processing, analytics, and visualization. Additionally, it explores the relevance of the PageRank algorithm in real-time contexts, highlighting its applications in personalized recommendations, fraud detection, and social media analytics.

Uploaded by

Gaming Ankur
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

RealTime Big Data Models

Module 5

James DSouza
What is Real-Time?

Real-time refers to the ability to process data and provide
outputs almost instantaneously after the data is received.

In computing and data processing, real-time systems are
designed to handle tasks within a strict time constraint,
often in milliseconds (0.001 seconds) or microseconds
(0.000001).


This is crucial for applications where timely processing is
essential, such as:
– Financial trading systems: Where stock prices need to be updated
and transactions executed in real-time.
– Healthcare monitoring: Where patient vitals are continuously
monitored and alerts are generated immediately if any parameter goes
out of range.
– Autonomous vehicles: Where sensors and cameras need to process
data in real-time to make driving decisions.
Real-Time Big Data Model

A real-time big data model is a framework
designed to handle and process large
volumes of data as it is generated, providing
immediate insights and actions.

This model is essential for applications that
require up-to-the-minute data analysis and
decision-making.
Real-Time Big Data Model

Here are some key components
– Data Ingestion
– Data Storage
– Data Processing
– Data Analytics and Query
– Data Visualization
Real-Time Big Data Model
Architecture of Data Stream Management System
Data
= Processing

Real-Time Big Data Model


Data Query and
Analytics
Data Data Data
Source Ingestion Storage

Data
Visualization

Data clients
(ML, Datawarehouse,
Applications)
Page Rank
Exam question
Structure of the Web

The structure of the web can be visualized in
several ways, but one common and effective
method is through a hierarchical model.

This model organizes web pages in a tree-like
structure, starting from a general homepage
and branching out into more specific subpages.
Structure of the web

Here’s a simple diagram to illustrate this:
Structure of the web

Key Components of Web Structure

Homepage: The central node that serves as the main
entry point to the website.

Top-Level Pages: These are the main categories or
sections of the website, such as “About Us,” “Services,”
and “Contact.”

Subpages: These provide more detailed information
and are nested under the top-level pages. For example,
under “Services,” you might have “Web Development”
and “App Development.”
Structure of the web
Types of Website Structures

Linear Model: Pages are arranged in a sequential
order, suitable for step-by-step processes.
Structure of the web
Types of Website Structures

Hierarchical Model: A tree-like structure with a
clear parent-child relationship, ideal for content-
heavy websites.
Structure of the web
Types of Website Structures

Webbed Model: A network-like matrix structure
where pages are interconnected through internal
links, allowing for more flexible navigation.
Structure of the web

Importance of Web Structure

User Experience: A well-organized structure helps
users find information quickly and easily.

SEO: Search engines can crawl and index a well-
structured website more effectively, improving
search rankings.

Maintenance: It simplifies website management
and updates, making it easier to add or modify
content.
Structure of the web

From a big data perspective, the structure of the
web can be visualized as a complex network of
interconnected nodes, where each node
represents a web page and the edges (links)
represent the hyperlinks between them. This
structure is often referred to as a web graph
Structure of the web

Here’s a simplified diagram to illustrate this
concept:
Structure of the web

Key Components of the Web Structure in Big Data

Nodes (Web Pages): Each node in the web graph represents a web page.
These pages contain various types of content, such as text, images,
videos, and links to other pages.

Edges (Hyperlinks): The edges represent the hyperlinks that connect one
web page to another. These links are crucial for navigation and for search
engines to crawl and index the web.

Clusters: Groups of web pages that are closely connected to each other
form clusters. These clusters often represent related content or topics.

Hubs and Authorities: In the context of web structure, hubs are pages
that link to many other pages, while authorities are pages that are linked to
by many other pages. These concepts are important for understanding the
flow of information and the importance of certain pages.
Structure of the web
Importance of Web Structure in Big Data

Data Collection: Understanding the web structure helps in efficiently
crawling and collecting data from the web. This is essential for building
large datasets for analysis.

Search Engine Optimization (SEO): Analyzing the web graph helps in
improving the visibility of web pages in search engine results by
optimizing the link structure.

Recommendation Systems: The web structure can be used to build
recommendation systems that suggest relevant content to users based
on their browsing patterns and the link structure.

Community Detection: Identifying clusters and communities within the
web graph can reveal groups of related content, which is useful for
targeted marketing and content delivery.

Centrality Measures: Calculating centrality measures (like PageRank)
helps in identifying the most influential pages within the web graph.
Page Rank Overview

Page Rank is an algorithm

Developed by Larry Page and Sergey Brin at
Stanford University in 1996.

An algorithm used by Google Search to rank
web pages in their search engine results.
Page Rank Overview

Page Rank is an algorithm

Developed by Larry Page and Sergey Brin at
Stanford University in 1996.

An algorithm used by Google Search to rank
web pages in their search engine results.

PageRank, while traditionally used for ranking
web pages, is highly relevant in the context of
real-time big data models
Relevance of PageRank in Real-
Time Big Data Models

Real-Time Graph Processing:
– Dynamic Graphs:

In real-time big data environments, graphs representing
relationships (like social networks or web links) are constantly
evolving.

Real-time PageRank algorithms can update rankings as new
data (nodes and edges) is ingested.
– Stream Processing:

Tools like Apache Flink and Apache Kafka Streams can be used
to process graph data streams in real-time, applying
PageRank to continuously update the importance of nodes.
Relevance of PageRank in Real-
Time Big Data Models

Personalized Recommendations:
– Real-Time Recommendations:

PageRank can be adapted to provide real-time personalized
recommendations.

For instance, in social networks, it can rank content or users
based on their relevance to a specific user, updated in real-
time as new interactions occur.
– Top-k Queries:

Real-time top-k PageRank queries can be used to identify
the most relevant nodes (e.g., most influential users or
trending content) in large-scale graphs
Relevance of PageRank in Real-
Time Big Data Models

Fraud Detection:
– Anomaly Detection:

In financial systems, real-time PageRank can help detect
anomalies by identifying unusual patterns in transaction
networks.

Nodes (accounts) with sudden changes in their
PageRank might indicate fraudulent activity.
– Network Security:

Similarly, in cybersecurity, real-time PageRank can help
identify compromised nodes in a network by analyzing
communication patterns
Relevance of PageRank in Real-
Time Big Data Models

Search and Information Retrieval:
– Real-Time Search Engines:

Search engines can use real-time PageRank to update the
ranking of web pages as new content is published and
linked.

This ensures that search results are always up-to-date and
relevant.
– Content Aggregation:

News aggregators and content platforms can use real-time
PageRank to rank articles and sources based on their
current relevance and popularity.
Relevance of PageRank in Real-
Time Big Data Models

Social Media Analytics:
– Influence Measurement:

Real-time PageRank can be used to measure the
influence of users or posts in social media networks. This
helps in identifying key influencers and trending topics as
they emerge.
– Engagement Tracking:

Platforms can track user engagement in real-time,
adjusting the visibility of posts and ads based on their
current PageRank.
Page Rank Overview

Implementation Considerations
– Scalability:

Implementing real-time PageRank requires scalable infrastructure capable of
handling large volumes of data and frequent updates.

Distributed computing frameworks like Apache Spark and GPU-based processing
can be leveraged for this
– Latency:

Ensuring low-latency updates is crucial for real-time applications.

Optimizations like incremental updates and parallel processing can help achieve this.
– Accuracy:

Balancing accuracy and computational efficiency is important.

Approximate algorithms and heuristics can be used to provide near-real-time results
with acceptable accuracy.
Page Rank overview

By integrating PageRank into real-time big data
models, organizations can enhance their ability
to analyze and act on data as it is generated,
leading to more timely and informed decisions.
Techniques for Efficient Computation

Sparse Matrix Representation:
– Description: Represent the web’s link structure as a sparse matrix to save
memory.
– Example: Only store non-zero entries.

Power Iteration Method:
– Description: Iteratively multiply the PageRank vector by the transition
matrix.
– Convergence: Typically converges in about 50 iterations.

MapReduce:
– Description: Distribute the computation across multiple machines.
– Implementation: Break the matrix into blocks or stripes to handle large
datasets.
Page Rank Algorithm
Power Iteration method

For every page,it counts the web links as
“votes” for authority

Page score = f(number of links)

High score = High relevance

Scores updated regularly for accuracy
Page Rank Algorithm
Power Iteration method

Total web pages in website = N

Each web page = vector = r0
= matrix of order n * 1
– The vector will contain the page scores for every single
web page
– The page score is initially assigned as 1/n to all nodes

Compute transition matrix Mn*n containing the
probability of making transition from one node to
every other node


Calculate next vector for every web page
– r1 = [M]n*n * [r0]n*1


Similarly calculate next vector r2 for every web
page
– r2 = [M]n*n * [r1]n *1

Similary

ri+1 = [M]n*n * [ri]n*1

Keep finding the next vector based on number
of iterations

The final distribution vector r is the page rank
of each webpage
Problem statement
Compute Matrix N * N
probability of transitioning from one node to another
Multiple with initial vector containing the page rank
1 iteration
st
2 iteration
nd
3 iteration
rd
Final Page Rank
Page Rank Algorithm
Power Iteration method – enhanced algorithm


Page Rank has drawback where it does not
consider a scenario where user may randomly
jump from one particular page to some different
page without using the links on the original
page

The modified algorithm introduces the
probability of jumping to a random page which
is called damping factor or taxation
Page Rank Algorithm
Power Iteration method – enhanced algorithm


The modified algorithm addresses issues such
as convergence, bias towards large websites
and vulnerability to link farms

The original matrix is recreated using the
damping matrix as
– A = damping factor * M + (1-damping factor) * [1/n]n*n
Page Rank Algorithm
Power Iteration method – enhanced algorithm
Page Rank Algorithm
Power Iteration method with taxation
Page Rank Algorithm
Power Iteration method with taxation
Page Rank Algorithm
Power Iteration method with taxation
Page Rank Algorithm
Power Iteration method with taxation
Page Rank Algorithm
Power Iteration method with taxation
Page Rank Algorithm
Power Iteration method with taxation
Page Rank Algorithm
Power Iteration method with taxation
Page Rank Algorithm
Power Iteration method with taxation
Page Rank Algorithm
Power Iteration method with taxation
Challenges in PageRank
Computation

Scalability:
– Issue: Handling billions of web pages.
– Solution: Use distributed computing frameworks like Hadoop.

Convergence Speed:
– Issue: Slow convergence of the power iteration method.
– Solution: Use techniques like Gauss-Seidel method or extrapolation
methods.

Memory Usage:
– Issue: Large memory requirements for storing the transition matrix.
– Solution: Use compressed sparse row (CSR) or column (CSC)
formats.
Techniques for Efficient Computation

Block Matrix Multiplication:
– Description: Divide the matrix into smaller blocks and process them
independently.
– Advantage: Reduces memory usage and allows parallel processing.

Random Surfer Model:
– Description: Introduce a damping factor to account for random jumps.
– Formula:

Use of Graph Databases:
– Description: Store the web graph in a graph database for efficient
traversal.
– Example: Neo4j, Amazon Neptune.

Challenges and Solutions

Dangling Nodes:
– Issue: Pages with no outbound links.
– Solution: Add a teleportation factor to redistribute PageRank.

Spider Traps:
– Issue: Groups of pages that only link to each other.
– Solution: Adjust the damping factor to ensure eventual escape.

Dead Ends:
– Issue: Pages that lead to no other pages.
– Solution: Modify the transition matrix to include teleportation.
Efficient Computation of PageRank

Summary: Efficient computation of PageRank
involves optimizing memory usage, speeding up
convergence, and handling large-scale data.
Page Rank Iteration method using MapReduce

Step 1 Initialization:

Input: A graph representing web pages and their
links. Each page has an initial PageRank value,
typically set to ( 1/N) where ( N ) is the total
number of pages.

Output: Key-value pairs where the key is the
page ID and the value is the initial PageRank.
Mapper Input
(Key,Value) = (PageID, Initial Ranking)
Page Rank Iteration method using MapReduce

Step 2: Mapping:

Input: Key-value pairs from the initialization step.

Process: For each page, emit the PageRank contribution to
each of its linked pages.

Also, emit the structure of the graph to ensure it is
preserved ?

Output: Key-value pairs where the key is the linked page ID
and the value is the PageRank contribution.
– Example Mapper Output

(Key, Value) = (Linking Page ID, PageRankContribution)
Page Rank Iteration method using MapReduce

Step 3: Shuffling and Sorting:



Input: Key-value pairs from the mapping step.

Process: Group all contributions by the linked page
ID.

Output: Key-value pairs where the key is the linked
page ID and the value is a list of PageRank
contributions.
Output (Key, Values) goes towards Reducer
– Linked PageID, All PageRank Contributions
Page Rank Iteration method using MapReduce

Step 4: Reducing:

Input: Key-value pairs from the shuffling and sorting step.

Process: Sum the PageRank contributions for each page and
apply the damping factor to compute the new PageRank.


MR Formula =
beta * (sum of all values aka page contributions) + (1- beta)
* [1/N]n*n


Output: Key-value pairs where the key is the page ID and the
value is the updated PageRank.
Ouput (Key, Value) = (PageID, Updated PageRank)
Page Rank Iteration method using MapReduce

Step 5 Iteration:

Repeat the mapping, shuffling, and reducing
steps until the PageRank values converge (i.e.,
the change in PageRank values between
iterations is below a certain threshold)
Page Rank Iteration method using MapReduce


Example

Let’s consider a simple example with three pages: A,
B, and C.

Initialization
– Page A: 1/3
– Page B: 1/3
– Page C: 1/3
Three mappers will be created in this case
– (A, 1/3) (B, 1/3) (C, 1/3)
Page Rank Iteration method using MapReduce

Mapping

Assume the following links:
– A links to B and C
– B links to C
– C links to A

For Page A:
– Emit (B, 1/6) and (C, 1/6) (since A’s PageRank is split equally among its two links)

For Page B:
– Emit (C, 1/3) (since B’s PageRank is given entirely to C)

For Page C:
– Emit (A, 1/3) (since C’s PageRank is given entirely to A)
Page Rank Iteration method using MapReduce

Shuffling and Sorting



Group contributions by page:
– A: [1/3]
– B: [1/6]
– C: [1/6, 1/3]
Page Rank Iteration method using MapReduce


Step 4 Reducing

Sum contributions and apply damping factor
(e.g., 0.85):
– A: 0.85 * (1/3) + 0.15 * (1/3) = 0.2833
– B: 0.85 * (1/6) + 0.15 * (1/3) = 0.1917
– C: 0.85 * (1/6 + 1/3) + 0.15 * (1/3) = 0.525
Page Rank Iteration method using MapReduce


Iteration
– Repeat the mapping, shuffling, and reducing steps
until the PageRank values converge.
– This iterative process continues until the PageRank
values stabilize, indicating the relative importance of
each page.
Java example

Input file
A B,C
BC
CA

This input file represents a graph where:
– Page A links to pages B and C.
– Page B links to page C.
– Page C links to page A.
Map function example using Java
Reduce function example using
Java
Java example output

Output file
A 0.2833 B,C
B 0.1917 C
C 0.525 A

This output file shows the PageRank values after one
iteration:
– Page A has a PageRank of 0.2833 and links to pages B and C
– Page B has a PageRank of 0.1917 and links to page C.
– Page C has a PageRank of 0.525 and links to page A.
Modify java program to support
three iterations
The output files at each covergence
will look as follows
Use of Combiners to Consolidate
the Result Vector

Combiners in MapReduce are optional
components that act as mini-reducers. They
operate on the intermediate data generated by
the map phase before it is sent to the reduce
phase.

The primary purpose of combiners is to reduce
the volume of data transferred between the map
and reduce stages, thereby optimizing the
overall performance of the MapReduce job.
Use of Combiners to Consolidate
the Result Vector

How Combiners Work

Intermediate Data Reduction: After the map phase generates
key-value pairs, combiners aggregate these pairs locally on each
mapper node. This reduces the amount of data that needs to be
shuffled across the network to the reducers.

Local Aggregation: Combiners perform local aggregation of the
map output. For example, if the map phase produces multiple key-
value pairs with the same key, the combiner can sum these values
before sending them to the reducer.

Efficiency: By reducing the amount of data transferred, combiners
help in minimizing network congestion and improving the efficiency
of the MapReduce job
Use of Combiners to Consolidate
the Result Vector

In the context of PageRank computation, combiners play a crucial role in
consolidating intermediate results. Here’s how they are used:

Initial PageRank Calculation: During the map phase, each page emits
its PageRank contribution to its linked pages. This results in a large
number of intermediate key-value pairs where the key is the linked page
and the value is the PageRank contribution.

Combiner Aggregation: The combiner aggregates these contributions
locally on each mapper node. For instance, if a page receives multiple
contributions from different pages, the combiner sums these contributions
before sending them to the reducer.

Reducer Efficiency: By the time the data reaches the reducer, the
volume of data is significantly reduced, making the reduce phase more
efficient. The reducer then finalizes the PageRank values for each page
based on the aggregated contributions3.

Using combiners in PageRank computation helps in handling large
datasets more efficiently by reducing the amount of intermediate
data that needs to be processed and transferred.
Java example of Combiner in PageRank
Java example of Combiner in PageRank
Recommendation System
A Model for Recommendation Systems

Definition: Recommendation systems are
algorithms designed to suggest relevant items
to users.

Purpose: They help users discover products,
services, or content they might be interested in.

Applications: Used in e-commerce (Amazon),
streaming services (Netflix), social media
(Facebook), and more.
A Model for Recommendation Systems

Key Components of a Recommendation
System
– User Profile
– Item Profile
– Utility Matrix
– Similarity Measures
– Recommendation Algorithm
Key Components of a
Recommendation System

User Profile:
– Contains user preferences, behavior, and interaction
history.
– Can be explicit (ratings, likes) or implicit (clicks,
views).
– Explicit Data: Ratings, reviews, likes, and
preferences provided by the user.
– Implicit Data: Browsing history, purchase history,
and interaction patterns.
User Profile example

Example:
{
"user_id": 1,
"age": 25,
"gender": "M",
"preferences": ["Action", "Comedy"],
"history": ["Movie1", "Movie2"]
}
Key Components of a
Recommendation System

Item Profile:
– Describes the attributes of items (e.g., genre, price,
features).
– Used in content-based filtering to match user
preferences.
– Attributes: Features that describe the item (e.g.,
genre, author, price).
– Metadata: Additional information such as tags,
categories, and descriptions.
Item Profile example

Example:
{
"item_id": 101,
"title": "Movie1",
"genre": ["Action", "Adventure"],
"rating": 4.5
}
Key Components of a
Recommendation System

Utility Matrix:
– A matrix representing user-item interactions.
– Rows represent users, columns represent items,
and cells contain ratings or interactions.
– Structure: Rows represent users, columns represent
items, and cells contain ratings or interactions.
– Sparsity: Most utility matrices are sparse, meaning
many cells are empty.
Utility Matrix Example

Example
Key Components of a
Recommendation System

Similarity Measures:
– Methods to calculate similarity between users or items.
– Common measures include cosine similarity, Pearson
correlation, and Jaccard index.
– Cosine Similarity: Measures the cosine of the angle between
two vectors.
– Pearson Correlation: Measures the linear correlation between
two sets of data.
– Jaccard Index: Measures the similarity between two sets by
comparing the size of their intersection to the size of their
union.

Similarity Measures: Cosine Similarity


Definition:
– Cosine similarity measures the cosine of the angle
between two vectors in a multi-dimensional space.
– It is often used to measure the similarity between
documents in text analysis.
– Formula
Similarity Measures: Cosine Similarity

Formula


Vector Dot Product of two Vectors divided by Magnitude Length Product of
two vectors

Interpretation:
– The value ranges from -1 to 1.
– A value of 1 means the vectors are identical,
– 0 means they are orthogonal (no similarity),
– and -1 means they are diametrically opposed.
Similarity measures: Pearson Correlation

Example: Consider two users with movie ratings represented as


vectors:

User 1: (Vector of User A ratings = [5, 3, 0, 1])

User 2: (Vector of User B ratings = [4, 0, 0, 1])

The cosine similarity would be calculated as:


An answer of 0.86 means the two users have similar taste for movies.
So if User A likes movie X, then User B may also like movie X
Key Components of a
Recommendation System

Recommendation Algorithm:
– The core algorithm that generates recommendations.
– Examples include

matrix factorization,

k-nearest neighbors,

deep learning models.
– Matrix Factorization: Decomposes the utility matrix into lower-
dimensional matrices.
– k-Nearest Neighbors (k-NN): Finds the k most similar users or items.
– Deep Learning Models: Uses neural networks to learn complex
patterns in data.
k-Nearest Neighbors (k-NN)


k-NN finds the k most similar users or items based on their
features. M1 M2 M3 M4 M5
U1 5 3 4 4 ?

Steps: U2 3 1 2 3 3
U3 4 3 4 3 5
– Utility Matrix: The original ratings matrix. U4 3 3 1 5 4
– Similarity Calculation: Compute similarity between users or items
using measures like cosine similarity or Pearson correlation.
– k-NN Search: For a given user or item, find the k most similar
users or items.
– Prediction: Aggregate ratings from the k-nearest neighbors to
predict ratings for unrated items.
A Model for Recommendation Systems

Recommendation systems are essential tools
for personalizing user experiences.

Understanding the key components and
algorithms helps in designing effective
recommendation systems.

Continuous improvement and adaptation are
crucial for maintaining relevance and accuracy.
A Model for Recommendation Systems

Types of Recommendation Systems
– Content-Based Filtering
– Collaborative Filtering
– Hybrid Systems
Recommendation Systems
Content Based Recommendation

Focus: Uses the features of items to make
recommendations.

Data: Relies on item metadata (e.g., genre, director,
actors for movies).

User Profile: Builds a profile of user preferences based
on the features of items they have interacted with.

Recommendation: Suggests items similar to those the
user has liked in the past.

Items with similar metadata
Content Based Filtering

Example: If a user likes action movies, the
system recommends other action movies based
on the genre feature.

Pros:
– Can recommend new or unpopular items.
– No need for user interaction data from other users.

Cons:
– Limited by the quality and availability of item
features.
– May not capture complex user preferences.
Collaborative Filtering

Focus: Uses the interactions between users and
items to make recommendations.

Data: Relies on user-item interaction data (e.g.,
ratings, clicks).

User/User or Item/Item Similarity: Finds similar
users or items based on interaction patterns.

Recommendation: Suggests items that similar
users have liked (user-based) or items similar to
those the user has liked (item-based).
Collaborative Filtering based
recommendation

Example: If a user likes a particular movie, the system
recommends movies that other users with similar
tastes have liked.

Pros:
– Can capture complex user preferences.
– Does not require detailed item features.

Cons:
– Struggles with new or unpopular items (cold start problem).
– Requires a large amount of interaction data.
Key Differences Between Content
Filtering and Collaborative

Data Dependency:
Filtering
– Content-Based: Depends on item features.
– Collaborative Filtering: Depends on user-item interactions.

Recommendation Basis:
– Content-Based: Recommends items similar to those the user has liked.
– Collaborative Filtering: Recommends items liked by similar users or similar to
those the user has liked.

Cold Start Problem:
– Content-Based: Less affected, can recommend new items based on features.
– Collaborative Filtering: More affected, struggles with new users/items without
interaction data.

Complexity of Preferences:
– Content-Based: May miss complex user preferences.
– Collaborative Filtering: Better at capturing complex preferences through
interaction patterns.
Content Based Recommendations

How It Works:

Item Features: Each item is described by a set of
attributes.

User Profile: A profile is created for each user
based on their interactions with items.

Similarity Calculation: The system calculates the
similarity between the user’s profile and the items’
attributes to recommend items that are similar to
those the user has liked in the past
Content Based Recommendations

Examples: Provide Examples of Content-Based Recommendation
Systems

Content-based recommendation systems are widely used across
various domains. Here are some notable examples:

– Netflix: Recommends movies and TV shows based on the genres, actors, and
directors that a user has previously watched and rated highly2.
– Amazon: Suggests products based on the attributes of items that a user has
viewed or purchased, such as category, brand, and price range3.
– Spotify: Recommends songs and playlists by analyzing the characteristics of
the music a user has listened to, such as genre, tempo, and artist3.
– YouTube: Suggests videos based on the content of videos a user has watched,
including tags, descriptions, and titles
Exam question

FUSR
Content-Based Recommendation
System

In a real-time big data model, product
recommendations based on properties of a
product can be achieved using content-based
filtering.

This approach leverages the attributes or
features of products to recommend similar
items to users.
How Content-Based Filtering Works


Feature Extraction

User Profile Creation

Similarity Calculation

Recommendation Generation
How Content-Based Filtering Works


Feature Extraction:
– Each product is described by a set of features or
properties.
– For example, in an e-commerce setting, a product like
a smartphone might have features such as

brand,

price,

screen size,

battery life,

camera quality, etc.
How Content-Based Filtering Works


User Profile Creation:
– A user profile is created based on the products they
have interacted with

Products viewed by user

Products liked by user

Products purchased by user
– This profile is essentially a vector that represents
the user’s preferences.
How Content-Based Filtering Works


Similarity Calculation:
– The system calculates the similarity between the
user’s profile and the available products.
– This is often done using

cosine similarity

Euclidean distance, or other

similarity measures.
How Content-Based Filtering Works


Recommendation Generation:
– Products that are most similar to the user’s profile
are recommended.
– The process of new recommendations are
generated instantly in real-time, meaning as soon
as a

user interacts with a product,

their profile is updated
How Content-Based Filtering Works

Example

Let’s consider an e-commerce platform that sells books. Here’s how a real-time
recommendation system might work:

Feature Extraction: Each book is described by features such as genre, author,
publication year, price, and user ratings.

User Profile Creation: Suppose a user has shown interest in books by J.K.
Rowling and George R.R. Martin, primarily in the fantasy genre, with high user
ratings.

Similarity Calculation: The system calculates the similarity between the user’s
profile and other books in the database. For instance, it might find that books by
Brandon Sanderson (another fantasy author) with high ratings are similar to the
user’s preferences.

Recommendation Generation: The system recommends books by Brandon
Sanderson and other similar authors in the fantasy genre with high ratings.
How Content-Based Filtering Works


Real-Time Processing
– In a real-time big data model, this entire process happens
dynamically.
– As soon as the user interacts with a new book (e.g., views
or purchases it), their profile is updated, and new
recommendations are generated instantly.
– This requires efficient data processing and storage
solutions, such as NoSQL databases and stream
processing frameworks like

Apache Kafka

Apache Flink.
How Content-Based Filtering Works


Tools and Technologies
– NoSQL Databases: MongoDB, Cassandra, Redis
– Stream Processing: Apache Kafka, Apache Flink, Apache
Storm
– Machine Learning Libraries: TensorFlow, PyTorch, Scikit-
learn

By leveraging these technologies, real-time
recommendation systems can provide personalized
and timely suggestions, enhancing user experience
and engagement.
Exam question

IUSR
Collaborative Recommendation

The collaborative recommendation has similar
steps like that of content recommendation
except that in the first step instead of choosing
feature extraction to make a decision, you
choose user interactions as features
Collaborative Filtering

Collaborative filtering is a technique used by
recommender systems to predict a user’s
interests by collecting preferences from many
users.

The underlying assumption is that if users
agreed in the past, they will agree in the future.

This method leverages the collective
intelligence of users to make personalized
recommendations.
Collaborative Filtering

How It Works:

User-Item Matrix: A matrix where rows represent
users and columns represent items. Each cell in
the matrix represents a user’s rating or
interaction with an item.

Similarity Calculation: The system calculates the
similarity between users or items to make
predictions about what a user might like based
on the preferences of similar users or items
Collaborative Filtering

Collaborative filtering can be broadly
categorized into two types:
– user-based
– item-based
Collaborative Filtering

User-Based Collaborative Filtering:

Definition: This method recommends items to a
user based on the preferences of similar users. It
identifies users who have similar tastes and
suggests items that those users have liked.

Example: If User A and User B have similar
ratings for several movies, and User A liked a
movie that User B hasn’t seen yet, that movie
will be recommended to User B
Collaborative Filtering

Item-Based Collaborative Filtering:

Definition: This method recommends items
based on the similarity between items. It looks at
the items a user has rated and finds similar
items to recommend.

Example: If a user liked a particular book, the
system will recommend other books that are
similar in content or genre to the one the user
liked
Case Study: Product Recommendation

Company: Amazon
Overview: Amazon uses a sophisticated product
recommendation system to enhance the
shopping experience for its users.

The system leverages collaborative filtering,
content-based filtering, and deep learning
algorithms to provide personalized
recommendations.
Case Study: Product Recommendation

Data Collection: Amazon collects data on user
interactions, such as browsing history, purchase
history, and product ratings.

Algorithm: The recommendation system uses a
combination of collaborative filtering (both user-based
and item-based) and content-based filtering to analyze
user preferences and item attributes.

Implementation: Recommendations are displayed on
various parts of the website, including the homepage,
product pages, and checkout page.
Case Study: Product Recommendation
Outcomes:


Increased Sales: Personalized recommendations have
significantly boosted Amazon’s sales. Studies show that up to 35%
of Amazon’s revenue is generated by its recommendation engine.

Enhanced User Experience: Users receive tailored suggestions
that match their interests, leading to a more engaging and
satisfying shopping experience.

Higher Conversion Rates: Personalized recommendations have
led to higher conversion rates, as users are more likely to
purchase items that are relevant to their preferences.
Case Study: Product Recommendation
Benefits:


Customer Retention: Personalized recommendations help in
retaining customers by providing a customized shopping
experience that encourages repeat visits.

Improved Customer Loyalty: Users are more likely to return to
Amazon for future purchases due to the personalized and
efficient shopping experience.

Data-Driven Insights: The recommendation system provides
valuable insights into customer behavior, helping Amazon to
refine its marketing strategies and inventory management
Social Networks as Graphs
What is a Graph?

Graph is a set of nodes and
edges connecting the nodes

It is more flexible than a tree in
that it can flow in any direction,
can have multiple parents, can
have more than two child
nodes.

A Graph enables to depict
complex relationships between
nodes, attributes of the nodes
itself
What is a Graph ?
Types of Graphs
Undirected Graphs:

Edges have no direction, representing
mutual relationships (e.g., friendships).
Directed Graphs:

Edges have a direction, representing
one-way relationships (e.g., follower-
following on social media).
Weighted Graphs:

Edges have weights, representing the
strength or frequency of interactions
Graph Theory


Graph theory is the study of graphs, which are
mathematical structures used to model pairwise
relations between objects
Unordered Undirected graph
Unordered Directed graph
What is a Social Network?

A social network is a group of people connected
by interpersonal relationships, or a website or
app that allows people to connect with each
other:
Social Networks as Graphs
Social Networks as Graphs:

Social networks can be represented as graphs
where nodes represent individuals or entities,
and edges represent relationships or
interactions between them.
Representation of Social Networks
as Graphs
Social Network as Graph can be represented
using various formats such as

Adjacency Matrix

Adjacency List

GEXF

GraphML

EdgeList
Representation of Social Networks
as Graphs
Adjacency Matrix:

A square matrix used to represent a finite graph (fixed vertices
and edges), with elements indicating the presence (bit value 1)
or absence (bit value 0) of an edge between nodes.

The diagonal of the matrix is always 0 because there are no
edges between a node and itself

If the graph is undirected, the adjacency matrix is symmetric.

Uses: Adjacency matrices can be used to identify clusters
within a graph, represent weighted graphs, and calculate
network properties like degree and centrality.
Representation of Social Networks
as Graphs
Adjacency Matrix:
Representation of Social Networks
as Graphs

Adjacency List:

A collection of lists or arrays used to represent
which nodes are adjacent to which other nodes.

It is implemented as an array, with each element
of the array representing a vertex in the graph

An adjacency list only stores the edges of a
graph, not the vertices, making it a space-
efficient representation of a graph
Adjacency List for Undirected graph
Vertex 0: [1, 2]

Vertex 1: [0, 2]

Vertex 2: [0, 1, 3]

Vertex 3: [2]
Adjancency List for a directed graph
Vertex 0: [1, 2]

Vertex 1: [0, 2]

Vertex 2: [1]
Adjacency matrix v/s Adjacency List
Adjacency matrix takes more space and hence it is more suited for
dense graph (lots of vertices and edges)

whereas Adjacency list takes less space and hence is suited for
sparse graphs (less vertices and less or no edges)
GEXF format to represent social
network graph
<graph>
<nodes>
<node id="1" label="Alice"/>
<node id="2" label="Bob"/>
<node id="3" label="Charlie"/>
</nodes>
<edges>
<edge source="1" target="2"/>
<edge source="2" target="3"/>
</edges>
</graph>
GraphML format to represent graph
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="[Link]
xmlns:xsi="[Link]
xsi:schemaLocation="[Link]

[Link]
<graph id="G" edgedefault="undirected">
<!-- Nodes -->
<node id="n0">
<data key="name">Alice</data>
</node>
<node id="n1">
<data key="name">Bob</data>
</node>
<node id="n2">
<data key="name">Charlie</data>
</node>

<!-- Edges -->


<edge source="n0" target="n1"/>
<edge source="n1" target="n2"/>
<edge source="n0" target="n2"/>
</graph>
</graphml>
EdgeList format to represent graph

Let’s consider a social network with four
people: Alice, Bob, Charlie, and David.
The friendships are as follows:

Alice Bob

Alice is friends with Bob and Charlie. Alice Charlie
Bob Charlie

Bob is friends with Charlie and David. Bob David
Charlie David

Charlie is friends with David.

The edge list for this social network
would look like this:
Representation of Social Networks
as Graphs

The other ways social network graph can be
represented is using
– Edge List: A list of all edges in the graph, where each
edge is represented by a pair (or tuple) of nodes.
– GraphML: An XML-based file format for graphs,
which supports both the structure and attributes of
the graph.
– GEXF: A language for describing complex networks
structures, their data, and dynamics.
Exam question
Varieties of Social Network Graph

A social network is a structure made up of
individuals or organizations (called nodes) that
are connected by one or more specific types of
interdependency, such as friendship, kinship,
common interests, financial exchanges,
dislikes, or relationships of beliefs, knowledge,
or prestige
Varieties of Social Networks
Varieties of Social Networks

Personal Networks: These are networks of personal
relationships, such as family, friends, and acquaintances.

Professional Networks: These include connections related to
one’s career, such as colleagues, mentors, and industry contacts.

Community Networks: These are networks within a community,
such as neighborhood groups, local clubs, or online communities.

Interest-Based Networks: These are formed around shared
interests or hobbies, such as book clubs, sports teams, or online
forums.

Organizational Networks: These involve connections within and
between organizations, such as business partnerships,
collaborations, and supply chains.
Varieties of Social Network Graphs
Need for Social Network Graphs
Social network graphs are essential for several reasons:

Visualization: They help visualize complex relationships and interactions
within a network, making it easier to understand the structure and
dynamics.

Analysis: They enable the analysis of network properties, such as
centrality, connectivity, and community structure, which can reveal
influential nodes and key connections.

Decision Making: They support decision-making processes by identifying
critical nodes and potential points of failure or opportunity within the
network.

Communication: They facilitate better communication and collaboration by
highlighting how information flows through the network.

Research: They are used in various fields of research, including sociology,
epidemiology, and marketing, to study patterns and effects of social
interactions.
Software for Social Network Graph
Visualization
Here are some popular tools you can use to visualize social
network graphs:

Pajek:
– A program for large network analysis.
– It is designed to handle large graphs and offers various visualization
and analysis features.

NodeXL:
– An Excel plugin that provides network analysis and visualization
capabilities.
– It is easy to use for those familiar with Excel.

InfraNodus:
– An online tool for network visualization and analysis.
– It offers features for text network analysis and can visualize
connections in data
Software for Social Network Graph
Visualization
Here are some popular tools you can use to visualize
social network graphs:

Gephi:
– An open-source graph visualization and exploration software.
– It supports various file formats like GraphML, GEXF, and more.
– It’s great for large networks and offers powerful analysis tools1.

SocNetV (Social Network Visualizer):
– A user-friendly, cross-platform tool for social network analysis
and visualization.
– It supports multiple file formats and provides various metrics
and algorithms for network analysis.

Examples of Social Network Graphs
Facebook Friendships:

Represented as an undirected graph where nodes are users
and edges are friendships
Twitter Followers:

Represented as a directed graph where nodes are users
and edges are follower-following relationships
LinkedIn Connections:

Represented as a weighted graph where nodes are users
and edges are connections with weights indicating
interaction frequency
Applications of Social Network
Analysis
Community Detection:

Identifying clusters or groups within a network.
Centrality Measures:

Determining the most important nodes in a
network.
Network Dynamics:

Studying how networks evolve over time
Applications of Social Network
Analysis
Community Detection:

Community Detection involves
identifying clusters or groups within
a network where nodes
(representing individuals,
organizations, etc.) are more
densely connected to each other
than to the rest of the network.

This is crucial for understanding
the structure and function of social
networks.
Applications of Social Network
Analysis
Community Detection Applications:

Marketing: Identifying communities can
help target specific groups with tailored
marketing strategies.

Epidemiology: Understanding how
diseases spread within communities can
help in designing effective intervention
strategies.

Social Media: Platforms like Facebook and
Twitter use community detection to suggest
friends or followers based on common
interests or connections.
Applications of Social Network
Analysis
Centrality Measures

Centrality Measures determine the most important nodes in a
network.

There are several types of centrality measures, each
highlighting different aspects of importance:
– Degree Centrality: Nodes with the most connections.
– Betweenness Centrality: Nodes that act as bridges between
different parts of the network.
– Closeness Centrality: Nodes that can reach other nodes most
quickly.
– Eigenvector Centrality: Nodes connected to other highly
connected nodes.
Types of Centrality
Applications of Social Network
Analysis
Centrality measures applications:

Influencer Identification: In social media,
centrality measures help identify key influencers
who can spread information widely.

Network Robustness: Identifying critical nodes
that, if removed, would disrupt the network.

Organizational Analysis: Understanding key
individuals or departments within an organization
that facilitate communication and workflow.
Applications of Social Network
Analysis
Network Dynamics

Network Dynamics involves
studying how networks evolve
over time.

This includes understanding
how nodes and edges
(connections) are added or
removed, and how these
changes affect the overall
network structure.
Applications of Social Network
Analysis

Network Dynamics Applications:
– Trend Analysis: In social networks, tracking how
trends emerge and spread over time.
– Innovation Diffusion: Understanding how new
ideas or technologies spread within a network.
– Policy Making: Analyzing how changes in policies
or regulations impact social structures and
relationships.
Clustering of Social Network Graphs

In social networks, clustering refers to the process of
identifying groups of nodes (individuals, entities, etc.) that
are more densely connected to each other than to the rest
of the network.

These groups, often called communities or clusters,
represent subsets of the network where members have
stronger interactions or similarities with each other
compared to those outside the group.

For example, in a social media network, a cluster might
represent a group of friends who frequently interact with
each other.
Clustering techniques

There are several techniques used for clustering
in social networks, each with its own strengths and
applications:
– K-Means Clustering
– Heirarchical Clustering
– Spectral Clustering
– Density-based Clustering (DBSCAN)
– Community Detection Algorithm
– Stochastic Block Models (SBM)
Direct Discovery of Communities in
a Social Graph

What is Community Detection ?

Community detection in social network graphs refers to the
process of identifying groups of nodes (communities) that are
more densely connected internally than with the rest of the
network.

These communities often represent clusters of individuals with
common interests, frequent interactions, or similar
characteristics.

Detecting these communities helps in understanding the structure
and dynamics of social networks, revealing hidden patterns, and
facilitating targeted interventions or recommendations
Methods for Discovering Communities


There are several methods for discovering
communities directly in a social graph
– Modularity Optimization
– Girvan Newman algorithm
– Label Propagation
– Heirarchical Clustering
– Stochastic Block Models
– Random Walks
– K- Clique Percolation
Girvan-Newman Algorithm
Girvan-Newman Algorithm Steps to identify
communities : cBC rEHB rB r

1 Calculate Betweenness Centrality


2 Remove Edge with Highest Betweenness
3 Recalculate Betweenness
4 Repeat
Girvan-Newman Algorithm
1 Calculate Betweenness Centrality:
– Compute the betweenness centrality for all edges in
the network.
– Betweenness centrality measures the number of
shortest paths that pass through each edge.
2 Remove Edge with Highest Betweenness:
– Identify and remove the edge with the highest
betweenness centrality.
Girvan-Newman Algorithm

3 Recalculate Betweenness:
– After removing an edge, recalculate the
betweenness centrality for all remaining edges.
4 Repeat till no edges left
– Continue removing edges with the highest
betweenness centrality and recalculating until the
network splits into distinct communities.
Exam question
Girvan-Newman Algorithm
Girvan-Newman Algorithm
Girvan-Newman Algorithm
Girvan-Newman Algorithm
Girvan-Newman Algorithm
Girvan-Newman Algorithm
Girvan-Newman Algorithm
Girvan-Newman Algorithm
Exam question
Exam question
Clique Percolation Method

What is a Clique?
In a social network graph, a clique is a subset of
nodes such that every two distinct nodes are
adjacent.

In other words, a clique is a complete subgraph
where every node is directly connected to
every other node within the clique.
Clique Percolation Method (CPM)

What is Overlapping Community?

These are groups of nodes in a social network
where nodes can belong to multiple cliques.

This reflects the real-world scenario where
individuals can be part of different social circles,
such as family, friends, and colleagues.
Clique Percolation Method (CPM)

The Clique Percolation Method (CPM) is used
– to detect overlapping communities in a network.
– It identifies communities by finding k-cliques
(complete subgraphs of k nodes)
– and then linking these k-cliques if they share (k-1)
nodes.
IBF
Clique Percolation Method (CPM)

Here is a simplified version of the CPM algorithm:
1. Identify k-Cliques:

Find all k-cliques in the graph.

2. Build Clique Graph:



Create a clique graph where each node represents a k-clique,
and there is an edge between two nodes if their corresponding k-
cliques share (k-1) nodes.

3. Find Connected Components:



Identify connected components in the clique graph.

Each connected component represents a community.
Clique use cases
Clique example
Clique example
Clique example
Clique and Community

Define community for clique with k nodes
Community of cliques example

How many cliques can you see ?

What is the size of each clique ?


We can see two cliques

Clique 1 with k=2 : A, B


Clique 2 with k=2 : B, C
Identify the Community
Community of cliques

How many cliques can you see ?

What is the size of each clique ?


Community of Cliques
Community of Cliques
Community of Cliques
Community of Cliques

k-1 = 2

For k=2, AB set of nodes, check if this is a common set of nodes belonging to more
than one clique to form a community

Since there is no other clique other than ABC, we write only clique number 1
Community of Cliques

k-1 = 2

For k=2, BC set of nodes, check if this is a common set of nodes belonging to more
than one clique to form a community

Since there is two cliques forming a community, clique 1 and clique 2, we show them
as above
Community of Cliques

k-1 = 2

For k=2, AC set of nodes, check if this is a common set of nodes belonging to more
than one clique to form a community

Since there is no clique forming a community, we keep the diagram as it is as clique 1


is already there
Community of Cliques

k-1 = 2

For k=2, BC, CD, BD set of nodes, there is no clique forming a community, we keep the
diagram
Community of Cliques

k-1 = 2

For k=2, DG set of nodes, there are two cliques forming a community, namely clique 3
and clique 6. So we add them to the diagram
Community of Cliques

k-1 = 2

For k=2, GH set of nodes, there are two cliques forming a community, namely clique 3
and clique 4. So we add them to the diagram
Community of Cliques

k-1 = 2

For k=2, DH set of nodes, there are two cliques forming a community, namely clique 3
and clique 5. So we add them to the diagram
Community of Cliques

k-1 = 2

For k=2, FG set of nodes, there are two cliques forming a community, namely clique 4
and clique 6. So we add them to the diagram
Community of Cliques

k-1 = 2

For k=2, GH set of nodes, there are two cliques forming a community, namely clique 3
and clique 4 which is already present in the diagram. So no change to diagram
Community of Cliques

k-1 = 2

For k=2, FH set of nodes, there are two cliques forming a community, namely clique 4
and clique 5. We add them to the diagram
Community of Cliques

k-1 = 2

For k=2, DF set of nodes, there are two cliques forming a community, namely clique 5
and clique 6. We add them to the diagram
Community of Cliques

k-1 = 2

For k=2, FH set of nodes, there are two cliques forming a community, namely clique 4
and clique 5 which is already present in the diagram. So no change to the diagram
Community of Cliques

k-1 = 2

For k=2, DH set of nodes, there are two cliques forming a community, namely clique 3
and clique 5 which is already present in the diagram. So no change to the diagram
Community of Cliques

k-1 = 2

For k=2, DF set of nodes, there are two cliques forming a community, namely clique 5
and clique 6 which is already present in the diagram. So no change to the diagram
Community of Cliques

k-1 = 2

For k=2, FG set of nodes, there are two cliques forming a community, namely clique 4
and clique 6 which is already present in the diagram. So no change to the diagram
Community of Cliques

k-1 = 2

For k=2, DG set of nodes, there are two cliques forming a community, namely clique 3
and clique 6 which is already present in the diagram. So no change to the diagram
Community of Cliques

k-1 = 2

For k-1=2, we have processed all possible combinations.

We can clearly see two independent communities formed

Community 1 is made up of two cliques namely clique 1 and clique 2


Community 2 is made up of four cliques namely clique 3, 4, 5 and 6
Community of Cliques

For k = 4, there is only one clique for all nodes are connecting to every other
node

Clique 1: D,F,H,G
Community of Cliques

For k = 4, there are no communities as there needs to be more than one


clique to form a community
Community of Cliques
Community of Cliques

For k = 3 clique, there are no k-1=2 common nodes between any two or more
cliques. Hence no communities can be formed.
Potential future developments in real-time big data models


Here are some potential future developments in
real-time big data models
– Advanced Analytics and AI-Powered Insights
– Edge Computing
– Real-time data governance and security
– Integration of Quantum Computing
– Data Democratization and Self-Service Analytics
– Ethical AI and Bias Mitigation
– Sustainable Data Management
Advanced Analytics and AI-Powered Insights


AI and Machine Learning:
– The integration of AI and machine learning will continue to
evolve, enabling more sophisticated and accurate real-
time analytics.
– These technologies will help in uncovering deeper insights
and making more precise predictions from streaming data.

Predictive Analytics:
– Enhanced predictive models will allow organizations to
anticipate trends and behaviors, leading to proactive
decision-making and improved operational efficiency
Edge Computing

Reduced Latency:
– By processing data closer to its source, edge
computing will significantly reduce latency, enabling
faster real-time analytics and decision-making.

Scalability:
– Edge computing will support the scalability of real-
time data processing, particularly in IoT applications
where vast amounts of data are generated at the
edge
Real-Time Data Governance and Security


Automated Governance:
– The implementation of automated data governance
frameworks will ensure data quality and compliance
in real-time, addressing privacy and security
concerns.

Enhanced Security Measures:
– As real-time data processing becomes more
prevalent, robust security protocols will be essential
to protect sensitive information from cyber threats
Integration of Quantum Computing

Quantum Algorithms:
– The advent of quantum computing will revolutionize
real-time data processing by solving complex
problems much faster than classical computers.

Data Encryption:
– Quantum computing will also enhance data
encryption methods, ensuring secure real-time data
transmission and storage
Data Democratization and Self-Service Analytics


Citizen Data Scientists:
– Empowering non-technical users with self-service
analytics tools will democratize data access,
allowing more individuals within organizations to
perform real-time data analysis.

Intuitive Visualization:
– Advanced data visualization platforms will make it
easier for users to interpret real-time data and
derive actionable insights
Ethical AI and Bias Mitigation

Fair and Transparent AI:
– Developing AI algorithms that are fair, transparent,
and unbiased will be crucial to ensure ethical real-
time data analysis.

Continuous Monitoring:
– Ongoing monitoring and testing of AI models will
help in identifying and mitigating biases in real-time
Sustainable Data Management

Green Computing:
– The push towards environmentally friendly data
processing methods will lead to the development of
sustainable real-time data management practices.

Efficient Resource Utilization:
– Optimizing the use of computational resources will
reduce the environmental impact of real-time data
processing

You might also like