Lecture

Graph Statistics: Random Graphs, Graph Homomorphisms, and Network Analysis

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications. ...

Description

This lecture by the instructor covers topics related to graph statistics, including random graph generation, graph homomorphisms, and network analysis. The lecture delves into the definition of functional t(F, G) for two graphs F and G, the metric for comparing networks, and practical approaches for comparing graphs. It also discusses network descriptors, fitting network models, and non-parametric summaries such as centrality measures like closeness centrality, harmonic centrality, and betweenness centrality. The lecture concludes with a discussion on clustering coefficients and parametric properties of graphs.

Instructor

Sofia Charlotta Olhede

I am a professor of Statistics at EPFL. I did my PhD in Mathematics at Imperial College London, and graduated in 2003. I was an assistant professor (lecturer) at Imperial College London 2002-2006, and an associate professor (senior lecturer) 2006-2007. In 2007 I moved to University College London and became a full professor. I moved to EPFL in 2019, and in 2018 I became an Institute of Mathematical Statistics Fellow with citation “For seminal contributions to the theory and application of large and heteroge

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (32)

Cluster analysis

Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters). It is a main task of exploratory data analysis, and a common technique for statistical data analysis, used in many fields, including pattern recognition, , information retrieval, bioinformatics, data compression, computer graphics and machine learning.

Social network analysis

Social network analysis (SNA) is the process of investigating social structures through the use of networks and graph theory. It characterizes networked structures in terms of nodes (individual actors, people, or things within the network) and the ties, edges, or links (relationships or interactions) that connect them. Examples of social structures commonly visualized through social network analysis include social media networks, meme spread, information circulation, friendship and acquaintance networks, peer learner networks, business networks, knowledge networks, difficult working relationships, collaboration graphs, kinship, disease transmission, and sexual relationships.

Centrality

In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, super-spreaders of disease, and brain networks. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.

Dynamic network analysis

Dynamic network analysis (DNA) is an emergent scientific field that brings together traditional social network analysis (SNA), link analysis (LA), social simulation and multi-agent systems (MAS) within network science and network theory. Dynamic networks are a function of time (modeled as a subset of the real numbers) to a set of graphs; for each time point there is a graph. This is akin to the definition of dynamical systems, in which the function is from time to an ambient space, where instead of ambient space time is translated to relationships between pairs of vertices.

Homomorphism density

In the mathematical field of extremal graph theory, homomorphism density with respect to a graph is a parameter that is associated to each graph in the following manner: Above, is the set of graph homomorphisms, or adjacency preserving maps, from to . Density can also be interpreted as the probability that a map from the vertices of to the vertices of chosen uniformly at random is a graph homomorphism. There is a connection between homomorphism densities and subgraph densities, which is elaborated on below.

Related lectures (64)

Statistical analysis of network data

Covers stochastic properties, network structures, models, statistics, centrality measures, and sampling methods in network data analysis.

Statistical Analysis of Network Data: Structures and Models

Explores statistical analysis of network data, covering graph structures, models, statistics, and sampling methods.

Handling Network Data

Explores handling network data, including types of graphs, real-world network properties, and node importance measurement.

Stochastic Blockmodel Estimation

Explores Stochastic Blockmodel estimation, spectral clustering, network modularity, Laplacian matrix, and k-means clustering.

Handling Networks: Graph Theory