Web Science Summary

Summary for the final exam of 188.921 Web Science at Vienna University of Technology.

It is available here

Some good readings

• http://www.cs.cornell.edu/home/kleinber/networks-book/
• http://barabasi.com/networksciencebook/

Tools used in the course

• igraph
• gephi
• http://www.cytoscape.org/

chapter 1

Studying the web lets you learn something about society. It is interdisciplinary. Challenges are - identify useful data - deal with winner takes all phenomenon in networks

Network structure

• vertices
• edges

Levels of analysis

• Element level
  • what is the most important element / how important is it
  • centrality indices (degree, betweenness, closeness, pagerank, hub & authorities)
• Group level
  • communities of common interests / preferences
  • decomposition into natural groups
  • local density analysis (clicques, clustering)
  • connectivity (strongly connected components)
• Network level
  • statistical propertis of large graphs
  • analysis of large networks
  • power law winner takes all (preferential attachment, scale free network)
  • small world property: average distance very short
  • structure of web is similar to bowtie, one huge strongly connected component

Social network analysis assumptions

• structural relations are more important than observed behaviour (age, ideology, gender)
• social relations affect actions, beliefs of individuals
• structural relations are dynamic

Bavelas experiemts with structures ( descriptive)

• The wheel (star ) and Y were considerably faster, on average, than the chain and circle.

Stanley Milgram - small world experiment

• Letter should reach target as soon as possible, so it be forwarded to person that knows target more likely
• but only close friends were allowed as destination, no direct connection
• quite some letters arrivec correctly

• interestingly average path length was very small (6) Erdös number

• same concept

chapter 2 - BASIC CONCEPTS OF NETWORK THEORY

Königsberg Bridge Problem

• pass through all the edges without visiting one twice
• route only exist if at most two vertices with odd degree exist

Metrics - Degree number of edges of a node - indegree #Incoming edges - outdegreee #ofOutgoing - average xxDegree average of one of the degrees menitoned before

Total number of eges

• undirected \(L=\frac{1}{2}\sum_{i=1}^{N}k_i\)
• directed \(L=\frac{1}{N}\sum_{i=1}^{N}k_i= \frac{2L}{N}\)

Average in degree = average outdegree for a directed network which is \(\frac{L}{N}\)

Adjacency matrix - defines the connections - often rather sparse - Convention: The direction of the edge runs form the second index to the first. (ie.e form top to left) - symmetric in case of undirected graphs - weighted graph as something else than 0,1 in the matrix - diagonal is 0 means no self loops

complete graph

• edge between each pair of vertices
• undirected max number of edges \(L=\frac{1}{2}N(N-1)\)
• directed max number of edges \(L=N(N-1)\)

density

• defined as the number of edges divided by maximum possible number of edges
• undirected \(p=\frac{L}{L_{max}}=\frac{2L}{N(N-1)}\)
• directed \(p=\frac{L}{L_{max}}=\frac{L}{N(N-1)}\)

Path - number of edges (hops) required to connect form A to B - distance is defined as shortest path - average distanc is mean of finite distances (i.e., shortest paths) between all pairs of vertices - cycle: at least three edges, if first and last vertex are the same - eulerian path: path which traverses each edge exactly once - diameter is longest distnace between all paris of vertices

practical exercises

Adjacency matrix

• Write down the corresponding adjacency matrices
• What is the average degree in each of the networks?

Density

• calculate network densities for a given network

Paths

• How many paths (with possible repetition of nodes and links) of length 3 exist in the network starting from node 1 and ending at node 3?
• What is the average distance in the network? And what the diameter?
• What is the length of the longest cycle in the network?
• Is there an Eulerian Path?

chapter 2.1 - BASIC CONCEPTS OF NETWORK THEORY (CONT.)

connectivity

• unidrected is connectd if there exists a path from every vertex to every other vertex
• directed is strongly connected if there is a directed path from every node to every other noded
• directed is weakly conneced if the path from every node to every other node exists only when ignoring the direction of the edges

connected component

• subgraph is using a subset of the vertices and edges of the original graph
• connected component is forming a subgraph with the maximal number of connected vertices
• when the graph is not connected the adjacency matrix can be rearranged to a block diagonal form
• for a directed graph
  • out components are the paths starting at A and including A
  • in paths which pass through A’s in part
• giant component contains significant fraction of all the nodes usually only one

network data representation

• matrix
• edge list
• graph

types of networks

• full network: contains all the nodes and edges, all entities are treated equally
• partial network: usually it is not possible to obtain a full network (i.e. twitter rate limit, or the full network is too large), is a subgraph
• egonetwork: consider networks from an entities point of view (my followers), may extend to any number of degrees from the ego (friends of friends)
• unimodal: contain only one type of vertex
• multimodal: vertices of different kinds are included
• bipartite network: multimodal with exactly 2 types of vertices ( groups and individuals, posts and comments)
• bipartite graph: vertices devided into disjoint sets that there only is an edge from one set to the other, no edges between vertices from the same edge
• multiplex networks have multiple types of connections

one mode projection

• transforms bipartite graphs into separate unimodal networks by two one mode projections
• possible loss of information
• example: recommendersystem books and likes
  • people are connected if they like the same book
  • books are connected if the same person likes them

practical part

• How many connected components are there in the network? What are their sizes? Are they weakly or strongly connected?
• Which nodes constitute the largest strongly connected component (SCC) of F?
• Which nodes belong to the IN-component of this SCC? Which nodes to its OUT-component?

• Name an edge you could add to increase the size of the SCC

• Write down the incidence matrix of the bipartite network.
• Construct the adjacency matrix of its two projections, on the purple and on the green nodes, respectively.
• What is the maximum number of links Lmax the network can have?

• How many links cannot occur compared to a non-bipartite, undirected network of size N = N1 + N2?

chapter 3 - CENTRALITY INDICES

todos for me

• do the exercises
• learn all the slides