Graph Mining and Information Network Analysis

Graph Mining

• Finding frequent subgraphs, substructures, chemical compounds, web fragments

Information Network Analysis

• Actors are objects or nodes.
• Relationships are edges.
• Examples: author networks in computer science, terrorist networks.
• A person can be part of multiple information networks
• Links carry semantic information.

Web Mining

• The web is a large information network like Google and PageRank
• Analysis includes usage mining, opinion mining, and web community discovery

Time and Ordering

• Trend, time-series, and deviation analysis: e.g., regression and value prediction
• Sequential pattern mining: e.g., buying a digital camera then a large SD memory card.
• Periodicity analysis: e.g., weekly sales spikes
• Biological sequence analysis: e.g., motifs
• Mining data streams: ordered, time-varying, potentially infinite data
• Conversational analysis

Evaluation

• Knowledge discovery, predictions, and assumptions are validated.
• Multi-dimensional evaluation includes: accuracy, interestingness, completeness, efficiency, explainability, diversity, and representativeness.

Application Areas

• Application areas include: E-commerce, social media, finance, insurance, telecommunications, transport, and data service providers

Major Challenges in Data Analysis (1): Mining Methodology

• Mining various and new types of knowledge
• Data analysis is an interdisciplinary effort.
• Handling noise, uncertainty, and incompleteness of data
• Pattern evaluation and pattern- or constraint-guided mining

Major Challenges in Data Analysis (2): User Interaction

• Interactive analysis
• Incorporation of background knowledge
• Presentation and visualization of data analysis results

Major Challenges in Data Analysis (3): Efficiency and Scalability

• Efficiency and scalability of data analysis algorithms
• Parallel, distributed, stream, and incremental analysis methods

Major Challenges in Data Analysis (4): Diversity of Data Types

• Handling complex types of data
• Analyzing dynamic, networked, and global data repositories

Major Challenges in Data Analysis (5): Data Analysis and Society

• Social impacts of data analysis
• Privacy-preserving data analysis

Data Objects and Attribute Types

• Data sets are made up of data objects.
• Each data object represents an entity.
• Examples: sales data: customers, store items, sales; medical data: patients, treatments, university data: students, professors, courses.
• Also called samples, examples, instances, data points, objects, or tuples.

Attributes

• An attribute is a data field that represents a characteristic of a data object.
• Examples: customer _ID, name, address
• Types include: nominal, binary, ordinal, numeric, interval-scaled, ratio-scaled.

Attribute Types: Nominal

• Categories, states, or “names of things”
• Examples: Hair color, marital status, occupation, ID numbers, zip codes

Attribute Types: Binary

• Nominal attributes with only 2 states (0 and 1)
• Symmetric binary: both outcomes equally important (e.g., gender)
• Asymmetric binary: outcomes not equally important (e.g., medical test)
• Convention: assign 1 to the most important outcome (e.g., HIV positive)

Attribute Types: Ordinal

• Values have a meaningful order (ranking) but magnitude between successive values is not known.
• Examples: Size = {small, medium, large}, grades, army rankings

Attribute Types: Numeric

• Quantity (integer or real-valued)
• Interval: measured on a scale of equal-sized units. Values have order. No true zero-point.
• Examples: temperature in C˚, calendar dates.
• Ratio: a numeric attribute with an inherent zero-point.
• Examples: 10istwiceashighas10 is twice as high as 10istwiceashighas5

Discrete vs.Continuous Attributes

• Discrete Attribute: has only a finite or countably infinite set of values.
• Examples: zip codes, profession, or the set of words in a collection of documents.
• Continuous Attribute: has real numbers as attribute values, measured and represented using a finite number of digits.
• Examples: temperature, height, or weight.

Some Special Data Formats

• Sequential data: ordered objects, time series, text data
• Graph data: nodes (vertices), edges (links)

Measuring the Central Tendency

• Mean (algebraic measure, sample vs.population): x = (åxi) / n
• Weighted arithmetic mean: x= (åwixi) / (åwi)
• Trimmed mean: chopping extreme values
• Median: middle value
• Mode: value that occurs most frequently

Symmetric vs.Skewed Data

• Median, mean and mode of symmetric, positively and negatively skewed data
• Positively skewed: mode<median<mean
• Negatively skewed: mean<median<mode

Measuring the Dispersion of Data

• Quartiles, outliers and boxplots
• Quartiles: Q1 (25th percentile), Q3 (75th percentile)
• Inter-quartile range: IQR = Q3 – Q1
• Five number summary: min, Q1, median, Q3, max
• Boxplot: ends of the box are the quartiles; median is marked; add whiskers, and plot outliers individually
• Outlier: usually, a value higher/lower than 1.5 x IQR
• Variance and standard deviation (sample: s, population: σ)
• Variance: s2 = (å (xi - x)2) / (n - 1)
• Standard deviation: s = the square root of the variance

Boxplot Analysis

• Five-number summary of a distribution: minimum, Q1, median, Q3, maximum
• Boxplot:
• Ends of the box are at the first and third quartiles, i.e., the height of the box is IQR
• Median is marked by a line within the box
• Whiskers: two lines outside the box extended to Minimum and Maximum
• Outliers: plotted individually, beyond a specified outlier threshold

Histogram Analysis

• Histogram: Graph display of tabulated frequencies, shown as bars
• Shows the proportion of cases falling into each interval

Similarity and Dissimilarity

• Similarity: Numerical measure of how alike two data objects are
• Value higher when objects are more alike
• Dissimilarity (e.g., distance): Numerical measure of how different two data objects are
• Lower when objects are more alike
• Proximity refers to a similarity or dissimilarity

Proximity Measure for Nominal Attributes

• Method 1: Simple matching: d (i, j) = p - (m / p)
• Method 2: Creating a new binary attribute for each of the M nominal states – then apply binary proximity measures

Proximity Measure for Binary Attributes

• Contingency table for binary data. Measures include a distance measure for symmetric binary variables, a distance measure for asymmetric binary variables, and the Jaccard coefficient (similarity measure for asymmetric binary variables)

Distance on Numeric Data: Minkowski Distance

• A popular distance measure: d (i, j) = ( (| xi1 - xj1 |h + | xi2 - xj2 |h +...+ | xip - xjp |h ) / (1 / h) )
• Properties:
• d(i, j) > 0 if i ≠ j, and d(i, i) = 0 (Positive definiteness)
• d(i, j) = d(j, i) (Symmetry)
• d(i, j) £ d(i, k) + d(k, j) (Triangle Inequality)
• A distance is a metric if it satisfies these properties.

Special Cases of Minkowski Distance

• h = 1: Manhattan (city block, L1 norm) distance
• h = 2: (L2 norm) Euclidean distance
• h ® ¥: Supremum (L¥ norm) distance