05 Module5 RealtimeBigDataModels
05 Module5 RealtimeBigDataModels
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
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 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
●
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
●
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>
●
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
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.
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
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 = 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 = 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