Data Warehousing and Data Mining

Clustering approaches

1. Partitioning methods: K-means, K-medoids (PAM), CLARA, CLARANS.
2. Hierarchical methods: agglomerative (AGNES), divisive (DIANA), BIRCH, CURE, Chameleon.
3. Density-based methods: DBSCAN, OPTICS, DENCLUE.
4. Grid-based methods: STING, CLIQUE, WaveCluster.
5. Model-based methods: EM / Gaussian mixture, COBWEB, SOM.

K-means algorithm

Input: $k$ (number of clusters) and a dataset of $n$ objects. Output: $k$ clusters.

1. Arbitrarily choose $k$ objects as initial cluster centres (means).
2. Repeat:
   1. Assign each object to the cluster whose mean is nearest, using distance $d(x,m_i)=\sqrt{\sum_j (x_j-m_{ij})^2}$.
   2. Recompute each cluster mean as the average of objects assigned to it.
3. Until assignments no longer change (or the squared-error criterion $E=\sum_{i=1}^{k}\sum_{x\in C_i}|x-m_i|^2$ converges).

Complexity is $O(nkt)$ for $t$ iterations.

Limitations

• The number of clusters $k$ must be specified in advance.
• Result depends on the initial centres and may converge to a local optimum.
• Works only where a mean is defined; unsuitable for categorical data.
• Sensitive to noise and outliers because the mean is distorted.
• Finds only spherical, similar-sized clusters; fails on arbitrarily shaped or density-varying clusters.
• Not scalable well for very high-dimensional data.

Classification by backpropagation

Backpropagation is a neural network learning algorithm used for classification. A multilayer feed-forward network has an input layer (one unit per attribute), one or more hidden layers and an output layer (one unit per class). Each connection has a weight, and each unit has a bias and an activation (usually sigmoid, $f(x)=1/(1+e^{-x})$).

Algorithm

1. Initialize weights and biases with small random numbers.
2. For each training tuple:
   • Forward pass: input is propagated, computing each unit's output $O_j=f(\sum_i w_{ij}O_i+\theta_j)$.
   • Backward pass: compute error. For output units $Err_j=O_j(1-O_j)(T_j-O_j)$; for hidden units $Err_j=O_j(1-O_j)\sum_k Err_k w_{jk}$.
   • Update: $w_{ij}=w_{ij}+l\cdot Err_j\cdot O_i$ and $\theta_j=\theta_j+l\cdot Err_j$, where $l$ is learning rate.
3. Repeat over epochs until the error is small or accuracy is acceptable.

It handles noisy data and learns complex nonlinear patterns, but training is slow and the result is hard to interpret.

Difference from Bayesian classification

Total transactions $=5$. Minimum support $=60\%\times5=3$ transactions.

C1 and L1 (counts): A=3, B=4, C=4, D=5. All are $\ge 3$, so $L_1=\{A,B,C,D\}$.

C2 and L2:

$L_2=\{AC, AD, BC, BD, CD\}$.

C3 and L3: joining gives ACD, BCD (ABC, ABD are pruned because AB is infrequent). Counts: ACD=3 (T1, T3, T5), BCD=3 (T2, T3, T5). Both are frequent, so $L_3=\{ACD, BCD\}$. No 4-itemset can be generated (ABCD contains infrequent AB).

Association rules (confidence $=\text{support(X∪Y)}/\text{support(X)}$, minimum 75%):

From ACD (3):

• A → CD: 3/3 = 100% (strong)
• C → AD: 3/4 = 75% (strong)
• D → AC: 3/5 = 60% (no)
• AC → D: 3/3 = 100% (strong)
• AD → C: 3/3 = 100% (strong)
• CD → A: 3/4 = 75% (strong)

From BCD (3):

• B → CD: 3/4 = 75% (strong)
• C → BD: 3/4 = 75% (strong)
• D → BC: 3/5 = 60% (no)
• BC → D: 3/3 = 100% (strong)
• BD → C: 3/4 = 75% (strong)
• CD → B: 3/4 = 75% (strong)

From 2-itemsets:

• A → C 100%, C → A 75%, A → D 100%, D → A 60% (no)
• B → C 75%, C → B 75%
• B → D 100%, D → B 80%
• C → D 100%, D → C 80%

All rules marked strong satisfy support $\ge60\%$ and confidence $\ge75\%$.

Text mining (text data mining) is the process of extracting useful, previously unknown patterns and knowledge from large collections of unstructured text such as documents, e-mails, news, web pages and social media posts.

Typical steps

1. Collect documents.
2. Preprocess: tokenization, stop-word removal, stemming, lowercasing.
3. Represent text, e.g. as a term-frequency / TF-IDF vector, $tfidf(t,d)=tf(t,d)\times\log\frac{N}{df(t)}$.
4. Apply mining techniques: classification, clustering, association, summarization, sentiment analysis, information extraction.
5. Interpret and evaluate results.

Example: A telecom company collects thousands of customer reviews and tweets. After preprocessing, a classifier labels each as positive, negative or neutral (sentiment analysis); frequent words in negative reviews such as "slow" and "network" show that internet speed is the main complaint. Other uses include spam filtering, news categorization and document clustering.

Social network analysis (SNA) studies relationships among entities (people, organizations, web pages) represented as a graph, where nodes are actors and edges are links such as friendship, follows or messages.

Steps

1. Collect data on actors and relations (social media, e-mail, surveys).
2. Build the graph (directed/undirected, weighted), stored as adjacency matrix or list.
3. Compute measures:
   • Degree centrality: number of links of a node.
   • Betweenness centrality: how often a node lies on shortest paths.
   • Closeness centrality: average distance to other nodes.
   • Density, clustering coefficient and path length.
4. Detect communities / clusters and key influencers.
5. Visualize and interpret results.

Uses

• Identifying influential people for marketing and spread of information.
• Detecting terrorist or fraud groups, and recommending friends or products.

An outlier is a data object that deviates significantly from the rest of the data, as if generated by a different mechanism. Outlier analysis (anomaly detection) identifies such objects, which may be errors (noise) or genuinely interesting events.

Methods: statistical (assume a distribution, flag values far from the mean, e.g. $|z|>3$ where $z=(x-\mu)/\sigma$), distance-based, density-based and clustering-based.

Example 1 (fraud detection): A customer normally spends Rs 2,000 to 5,000 per transaction with a credit card in Kathmandu. A sudden purchase of Rs 500,000 abroad deviates strongly and is flagged as a possible fraud.

Example 2: In student marks {55, 60, 58, 62, 57, 59, 5}, the mark 5 lies far from the cluster and is an outlier, perhaps a data entry error.

Other uses are intrusion detection, medical diagnosis and fault detection.

Why preprocessing is required

Real-world data is dirty. It may be incomplete (missing values), noisy (errors, outliers), inconsistent (different codes or units) and redundant, or too large. Poor quality data gives poor mining results ("garbage in, garbage out"). Preprocessing improves quality, accuracy and efficiency of mining.

Two methods

1. Data cleaning:

   • Missing values: ignore the tuple, fill manually, use a global constant, attribute mean, or the most probable value.
   • Noisy data: binning (smooth by bin means or boundaries), regression, clustering to detect outliers.
   • Inconsistencies are corrected and duplicates removed.

2. Data normalization (transformation): scale attribute values into a common range.

   • Min-max: $v'=\dfrac{v-\min}{\max-\min}(new\_max-new\_min)+new\_min$
   • Z-score: $v'=\dfrac{v-\mu}{\sigma}$

Other methods are data integration, data reduction and discretization.

Data mining functionalities specify the kinds of patterns that can be discovered. They fall into two broad groups: descriptive (characterise the general properties of the data) and predictive (use current data to make predictions).

1. Class/concept description: Summarises a class or concept in concise terms. Data characterization summarises the general features of a target class (e.g. customers who spend over Rs 50,000 a year). Data discrimination compares the target class with one or more contrasting classes.

2. Frequent patterns, association and correlation: Finds itemsets, subsequences or substructures that occur often. Association rules such as $\text{buys(milk)} \Rightarrow \text{buys(bread)}$ [support = 5%, confidence = 70%] are mined, and correlation analysis checks whether the associations are statistically meaningful.

3. Classification and prediction: Builds a model (decision tree, Naive Bayes, neural network, SVM) from training data with known class labels, then uses it to predict the class of new objects. Prediction estimates a continuous value (regression).

4. Cluster analysis: Groups objects into clusters without class labels, so that intra-cluster similarity is high and inter-cluster similarity is low (e.g. customer segmentation).

5. Outlier analysis: Detects objects that do not follow the general behaviour of the data. These may be noise, or may be useful, as in fraud detection.

6. Evolution and trend analysis: Describes regularities or trends of objects whose behaviour changes over time, such as time-series and sequential pattern analysis and stock-price movement.

(a) OLAP (Online Analytical Processing)

OLAP is a technology that lets users analyse multidimensional data interactively, from different viewpoints, using a data warehouse organised as a data cube. It supports decision-making with fast, complex queries over large historical data.

Main OLAP operations:

• Roll-up (drill-up): aggregate data by climbing a concept hierarchy or reducing dimensions (city to country).
• Drill-down: the reverse, moving to more detailed data (year to quarter to month).
• Slice: select one value of one dimension, giving a sub-cube.
• Dice: select values on two or more dimensions.
• Pivot (rotate): rotate the axes to give another view.

OLAP servers can be ROLAP (relational), MOLAP (array-based) or HOLAP (hybrid). OLAP differs from OLTP, which handles day-to-day transactions.

(b) Laplace Smoothing

In Naive Bayes classification, the posterior is a product of conditional probabilities $P(x_i \mid C)$. If an attribute value never occurs with some class in the training data, its estimate is $0$ and the whole product becomes $0$ (the zero-probability problem).

Laplace smoothing (add-one correction) adds $1$ to each count:

$P(x_i \mid C)=\frac{n_{ic}+1}{n_c+k}$

where $n_{ic}$ is the number of tuples of class $C$ with value $x_i$, $n_c$ the number of tuples of class $C$, and $k$ the number of distinct values of the attribute. For example, with 1000 tuples having income = low 0, medium 990, high 10, the corrected counts are 1, 991, 11 over 1003. The probabilities stay close to the originals but none is zero.

Full cube

A full cube is a data cube in which all cuboids (every group-by combination of dimensions, $2^n$ for $n$ dimensions without hierarchies) are fully materialised, with every non-empty cell computed and stored. It gives fast query answers but needs very large storage, because the number of cells grows exponentially with the number of dimensions. For example, with dimensions $A,B,C$ the full cube has the 8 cuboids $ABC, AB, AC, BC, A, B, C$ and the apex (all).

Beam search

Beam search is a heuristic search used for rule/pattern generation (for example in rule-based classifiers and top-$k$ pruning in cube mining). It is a limited version of breadth-first search, and it avoids exhaustive search.

Working mechanism:

1. Start with the most general hypothesis (empty rule or root node).
2. Generate all possible refinements of the current candidates (for example add one attribute test or move one level down).
3. Score every candidate with an evaluation function (accuracy, information gain, interest).
4. Keep only the best $k$ candidates, where $k$ is the beam width, and discard the rest.
5. Repeat steps 2 to 4 with the retained candidates until no improvement or a stopping condition is reached.
6. Return the best candidate found.

It uses far less time and memory than full breadth-first search. The cost is that it is not guaranteed to find the global optimum, since a good path may be pruned. With $k=1$ it becomes greedy hill climbing.

Conceptual modelling of a data warehouse describes the multidimensional structure of the data, using dimension tables and a central fact table. The main techniques are the star, snowflake and fact constellation schemas.

1. Star schema

• It has one large central fact table holding measures (e.g. units_sold, dollars_sold) and foreign keys to the dimensions.
• Around it are one dimension table per dimension (time, item, branch, location), each de-normalised and containing all levels of its hierarchy.
• The diagram looks like a star. Queries need few joins and run fast, but there is redundancy in the dimension tables.

2. Snowflake schema

• A variant of the star schema in which dimension tables are normalised into further tables. For example, the location dimension splits into location and city/state/country tables.
• It reduces redundancy and saves space and is easy to maintain, but it needs more joins, so queries are slower and the structure is more complex.

Fact constellation (galaxy) schema is a third technique: several fact tables share dimension tables, so it models multiple related subjects such as sales and shipping.

Data mining goals

• Description: find human-interpretable patterns that describe the data, such as clusters and associations.
• Prediction: use known data to predict unknown or future values, such as class labels or sales.
• Classification: assign objects to predefined classes.
• Clustering/segmentation: group similar objects with no predefined labels.
• Association discovery: find items that occur together.
• Outlier/anomaly detection: detect unusual records such as fraud.
• Trend and deviation analysis: study how data change over time.

Components of a data warehouse

A data warehouse is a subject-oriented, integrated, time-variant and non-volatile collection of data supporting management decisions. Its components are:

1. Data sources: operational databases, flat files, external data and legacy systems that supply the raw data.
2. ETL / data staging area: the tools that extract data from the sources, transform it (clean, integrate, convert formats, resolve inconsistencies) and load it into the warehouse, with periodic refresh.
3. Data warehouse database (central repository): the large database that stores the integrated, summarised and detailed historical data, usually organised multidimensionally as a star or snowflake schema.
4. Metadata repository: data about data, covering the warehouse structure and schema, source mappings, transformation rules, definitions, hierarchies and usage and access information.
5. Data marts: smaller subject-specific subsets of the warehouse for a department (sales, finance).
6. OLAP server: (ROLAP, MOLAP or HOLAP) presents the data multidimensionally and supports roll-up, drill-down, slice and dice.
7. Front-end/client tools: query and reporting tools, analysis tools and data mining tools used by end users.
8. Management and administration tools: monitor, secure, back up and manage the warehouse.

Market basket analysis

Market basket analysis finds associations between items that customers buy together in the same transaction. If customers who buy item A tend also to buy item B, this is written as the rule $A \Rightarrow B$. The results are used for shelf placement, cross-selling, promotions and catalogue design. For example, $\{\text{bread}\} \Rightarrow \{\text{butter}\}$.

Two measures define a rule:

$\text{support}(A\Rightarrow B)=\frac{\text{transactions containing }A\cup B}{\text{total transactions}},\qquad \text{confidence}(A\Rightarrow B)=\frac{\text{support}(A\cup B)}{\text{support}(A)}$

A rule is strong if it satisfies the minimum support and minimum confidence thresholds.

Apriori algorithm for frequent itemsets

The Apriori property says that every subset of a frequent itemset must also be frequent. Equivalently, if an itemset is infrequent, all of its supersets are infrequent, which is used to prune the search.

Steps:

1. Scan the database and count each item. Keep those with support at least min_sup to get $L_1$.
2. Join step: join $L_{k-1}$ with itself to form the candidate $k$-itemsets $C_k$.
3. Prune step: remove any candidate that has an infrequent $(k-1)$-subset.
4. Scan the database to count the supports of the remaining candidates. Those meeting min_sup form $L_k$.
5. Repeat steps 2 to 4 until $L_k$ is empty. The union of all $L_k$ is the set of frequent itemsets.
6. Generate rules from each frequent itemset by splitting it into $A$ and $B$ and keeping rules with confidence at least min_conf.

Example, with min support count 2 and transactions T1 = {A,B,C}, T2 = {A,C}, T3 = {A,D}, T4 = {B,C}:

• $L_1=\{A{:}3,\ B{:}2,\ C{:}3\}$ (D has count 1 and is dropped).
• $C_2=\{AB,AC,BC\}$ with counts $1,2,2$, so $L_2=\{AC,BC\}$.
• $C_3=\{ABC\}$ is pruned because its subset $AB$ is infrequent. The algorithm stops.

Gini index for attribute selection

The Gini index measures the impurity of a data partition $D$ (used in CART):

$Gini(D)=1-\sum_{i=1}^{m}p_i^2$

where $p_i$ is the proportion of tuples of class $C_i$. For a binary split on attribute $A$ into $D_1$ and $D_2$:

$Gini_A(D)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$

The attribute (and split subset) with the minimum $Gini_A(D)$, that is the largest reduction in impurity $\Delta Gini=Gini(D)-Gini_A(D)$, is chosen as the splitting attribute.

Example: 14 tuples of buys_computer, with 9 yes and 5 no.

$Gini(D)=1-\left(\tfrac{9}{14}\right)^2-\left(\tfrac{5}{14}\right)^2=0.459$

Income has low (3 yes, 1 no), medium (4 yes, 2 no) and high (2 yes, 2 no). Consider the split {low, medium} versus {high}:

• $D_1$ has 10 tuples (7 yes, 3 no), so $Gini(D_1)=1-0.49-0.09=0.42$.
• $D_2$ has 4 tuples (2 yes, 2 no), so $Gini(D_2)=1-0.25-0.25=0.5$.

$Gini_{income}(D)=\tfrac{10}{14}(0.42)+\tfrac{4}{14}(0.5)=0.300+0.143=0.443$

The reduction is $0.459-0.443=0.016$. The same is computed for the other subsets and attributes, and the one with the lowest Gini is chosen as the node.

Support Vector Machine (SVM)

SVM is a supervised classifier that finds the maximum-margin hyperplane separating two classes.

1. Each tuple is a point $\mathbf{x}$ in feature space with label $y=\pm1$.
2. A separating hyperplane is $\mathbf{w}\cdot\mathbf{x}+b=0$. Of the many possible hyperplanes, SVM picks the one with the largest margin $\frac{2}{\|\mathbf{w}\|}$ between the two classes.
3. The training points lying on the margin boundaries are the support vectors, and they alone define the hyperplane.
4. Training solves the optimisation problem: minimise $\frac{1}{2}\|\mathbf{w}\|^2$ subject to $y_i(\mathbf{w}\cdot\mathbf{x}_i+b)\ge1$. This is solved with Lagrange multipliers (a quadratic programming problem).
5. For non-separable data, a soft margin (parameter $C$) allows some errors. For non-linear data, a kernel function (polynomial, RBF) maps the data into a higher-dimensional space where it becomes linearly separable.
6. A new tuple is classified by the sign of $\mathbf{w}\cdot\mathbf{x}+b$.

SVMs are accurate and resist overfitting, but training is slow on large data.

An ordinal attribute has values with a meaningful order or rank, but the gap between values is unknown (e.g. grade: fair < good < excellent). Similarity is computed by converting the ranks to a numeric scale and then treating them as interval-scaled values.

Steps (for attribute $f$ with $M_f$ ordered states):

1. Replace each value $x_{if}$ by its rank $r_{if}\in\{1,\dots,M_f\}$.
2. Normalise each rank onto $[0,1]$ so that every attribute has equal weight:

$z_{if}=\frac{r_{if}-1}{M_f-1}$

3. Compute the dissimilarity with a distance measure such as Euclidean or Manhattan on the $z_{if}$ values, and similarity $=1-d$.

Example: test-2 has the states fair, good, excellent ($M_f=3$). Ranks 1, 2, 3 give $z=0,\ 0.5,\ 1$. For objects with values excellent, fair, good, fair the $z$ values are $1, 0, 0.5, 0$. The distance between the objects with excellent and good is $|1-0.5|=0.5$, so the similarity is $0.5$. Between excellent and fair, $d=1$ and the similarity is $0$.

When there are several ordinal attributes, the per-attribute distances are combined, for instance by Euclidean distance. If they are mixed with other attribute types, the weighted combination $d(i,j)=\dfrac{\sum_f \delta_{ij}^{(f)}d_{ij}^{(f)}}{\sum_f\delta_{ij}^{(f)}}$ is used.

Example: if cell $(a_1,b_1,*)$ and its more specific cell $(a_1,b_1,c_1)$ both have count 5, the first is not closed. A closed cube stores only $(a_1,b_1,c_1)$, and $(a_1,b_1,*)$ is derived from it.

Lazy learners

A lazy learner stores the training tuples and does little work until a test tuple arrives. Only then does it generalise, by comparing the new tuple with the stored ones. Training is therefore very fast, but classification is slow and needs a lot of storage, because every prediction needs a scan or index search over the training data.

Examples are the k-nearest neighbour (k-NN) classifier, which assigns the majority class among the $k$ closest training tuples (by Euclidean distance), case-based reasoning and locally weighted regression. They can model complex decision boundaries, but they are sensitive to irrelevant attributes and need attribute scaling. Eager learners (decision trees, SVM, Naive Bayes) build a model first, in contrast.

Ensemble methods

An ensemble combines several base classifiers $M_1,\dots,M_k$ and classifies a new tuple by voting or averaging their predictions. A combination of diverse classifiers is usually more accurate than any single one and reduces variance, bias or overfitting.

Common methods:

• Bagging (bootstrap aggregating): each model is trained on a bootstrap sample (sampling with replacement) and the predictions are combined by majority vote. Random forest is bagged decision trees with random attribute selection.
• Boosting (e.g. AdaBoost): models are built sequentially. Misclassified tuples get higher weights so the next model focuses on them, and the final vote is weighted by each model's accuracy.
• Stacking: a meta-classifier learns how to combine the outputs of the base models.

Clustering works on an $n$ objects by $p$ variables data matrix (or an $n\times n$ dissimilarity matrix). The types of variables determine how similarity is measured.

1. Interval-scaled variables: continuous measurements on a linear scale (weight, height, temperature). They are standardised first, e.g. $z=\frac{x-\mu}{\sigma}$, and distance is computed with Euclidean $d=\sqrt{\sum(x_{i}-x_{j})^2}$, Manhattan or Minkowski distance.

2. Binary variables: two states, 0 and 1. For symmetric binary variables, $d(i,j)=\frac{r+s}{q+r+s+t}$. For asymmetric ones, the Jaccard measure $d(i,j)=\frac{r+s}{q+r+s}$ is used. Here $q$ is the number of positions where both are 1, $r$ and $s$ those where they differ, and $t$ where both are 0.

3. Nominal (categorical) variables: more than two unordered states (colour). The dissimilarity is $d(i,j)=\frac{p-m}{p}$, where $m$ is the number of matches and $p$ the number of variables.

4. Ordinal variables: ordered states (rank). Ranks are mapped to $[0,1]$ by $z=\frac{r-1}{M-1}$ and treated as interval-scaled.

5. Ratio-scaled variables: positive measurements on a non-linear scale, such as exponential growth. A logarithmic transformation is applied before treating them as interval-scaled.

6. Mixed-type variables: real data has several types together. The dissimilarities of each type are combined into one by the weighted formula $d(i,j)=\frac{\sum_f\delta_{ij}^{(f)}d_{ij}^{(f)}}{\sum_f\delta_{ij}^{(f)}}$.

Outlier

An outlier is a data object that deviates significantly from the rest of the data, as if it were generated by a different mechanism. It may be caused by measurement error or noise, or may be a genuine rare event, as in credit-card fraud, intrusion or medical anomalies.

Clustering high-dimensional data

In high dimensions, many attributes are irrelevant and the distances between objects become nearly equal (the curse of dimensionality), so clusters hide in subspaces. Main approaches:

• Subspace clustering: search for clusters in subsets of dimensions, e.g. CLIQUE (grid-based and density-based, using the Apriori-like monotonicity of dense units) and PROCLUS (projected clustering).
• Dimensionality reduction: apply PCA, SVD or feature selection first and then cluster in the reduced space.
• Biclustering: cluster rows and columns together (e.g. genes and conditions).
• Frequent pattern based clustering for very high-dimensional data such as text, where frequent terms define the clusters.

Viral marketing

Viral marketing is a promotion strategy in which customers who like a product spread it to their friends and contacts through a social network, by word of mouth and online sharing. The marketer targets a small set of influential customers and the message spreads like a virus, so the cost is low. In data mining, the aim is to find the most influential nodes (the influence maximisation problem).

Densification power law

Real social and information networks become denser over time. The number of edges grows faster than the number of nodes, so the average degree increases instead of staying constant. Densification is expressed as

$e(t)\propto n(t)^{a}\quad\text{or}\quad e(t)=c\,n(t)^{a},\qquad 1\le a\le 2$

where $e(t)$ and $n(t)$ are the numbers of edges and nodes at time $t$. If $a=1$ the graph stays sparse (constant average degree), and if $a=2$ it becomes a clique-like, fully dense graph. Real networks have $1<a<2$, and the plot is a straight line on log-log axes with slope $a$. A related observation is that the effective diameter often shrinks as the network grows.

Neither can undo a merge or split once done, and both produce a dendrogram, which can be cut at a chosen level to obtain the clusters.

Social network analysis (SNA) studies relationships among people, groups or organisations, modelled as a graph with nodes (actors) and edges (ties). The main analyses are:

1. Link prediction: predict whether a link will form between two nodes in the future (friend suggestion) using the common neighbours, Jaccard coefficient or path-based measures.
2. Community detection (clustering): find densely connected groups of nodes, e.g. with modularity-based and hierarchical (Girvan-Newman) methods.
3. Centrality and influence analysis: find the important or influential nodes by degree, closeness, betweenness and eigenvector centrality (PageRank). This is used in viral marketing.
4. Classification of nodes/links: label nodes (spammer or genuine, interest group) from their attributes and neighbours.
5. Information diffusion analysis: study how information, ideas or diseases spread through the network.
6. Evolution analysis: study how the network grows over time (densification, shrinking diameter, power-law degree distribution, small-world property).
7. Sentiment and opinion mining of posts, and anomaly/fraud detection such as fake accounts.

Web mining applies data mining techniques to discover useful information from the World Wide Web. It has three categories.

1. Web content mining It extracts useful knowledge from the content of web pages, including text, images, audio, video and structured records. Tasks include page classification and clustering, information extraction, text summarisation, opinion mining and search-result mining. Techniques come from text mining and information retrieval, such as TF-IDF and keyword extraction.

2. Web structure mining It analyses the hyperlink structure of the web, treating pages as nodes and hyperlinks as edges of a graph. It discovers authoritative and important pages and communities, e.g. with the PageRank and HITS (hubs and authorities) algorithms. It is used to rank search results and to detect spam and web communities.

3. Web usage mining It discovers user access patterns from web logs (server logs, proxy logs, cookies, clickstreams). The process has pre-processing (data cleaning, user and session identification), pattern discovery (association rules, sequential patterns, clustering) and pattern analysis. It is used for site personalisation, recommendation, improving site design, caching and e-commerce marketing.