Social Network Analysis (TU Wien, Austria)
73 flashcards · Computer Science · by Locke Lamora
Graph
A graph G=(V,E)G=(V,E)G=(V,E) is an abstract object formed by a set VVV of vertices and a set EEE of edges connecting pairs of vertices
Directed/Undirected Graph
In an undirected graph the edges do not have an orientation. The order of the vertices that are connected by an edge is not important. In a directed graph (di-graph) each edge has an origin and a destination. Such edges are called directed edges (usually represented by lines with arrows on them).
Multigraph
A (undirected or directed) graph is called multigraph if the same edge occurs more than once (multiedge).
Self-Edge/Self-Loop
A self-edge or self-loop is an (undirected or directed) edge that links a vertex to itself.
Degree, average degree, total number of edges
In-degree/out-degree
In a directed graph each vertex has two degrees: The in-degree k1ink_1^{in}k1in is the number of connections coming to a vertex iii the out-degree kiout k_i^{out} kiout is the number of outgoing edges. It holds that : ki=kiin+kioutk_i = k_i^{in} + k_i^{out}ki=kiin+kiout
Adjacency (Matrix)
If two vertices are joined by an edge, they are adjacent and we call them neighbors. The adjacency matrix AAA of an undirected graph with NNN vertices (labeled with 1,…,N1,\dots,N1,…,N ) is the N×NN \times NN×N matrix with elements AijA_{ij}Aij such that The adjacency matrix AAA of a directed graph with NNN vertices (labeled with 1,…,N1,\dots,N1,…,N ) is the N×NN \times NN×N matrix with elements AijA_{ij}Aij such that In general, the adjacency matrix of a directed network is asymmetric. Remar…
Weighted/valued Graph
Unweighted resp. binary edges only indicate whether an edge exists or not. In a weighted or valued graph, each edge can be assigned an additional numerical value – representing, for example cost, speed, time, data flow or the strength of a link.
Complete Graph
In a complete graph there is an edge between each pair of vertices.
Density
where NNN is the number of vertices and LLL is the number of edges. LmaxL_{max} Lmax denotes the maximum number of edges in this graph. It holds that: 0≤ρ≤10 \leq \rho \leq 10≤ρ≤1
Path, Path Length and Distance
A path ppp in a graph G=(V,E)G= (V,E)G=(V,E) is a sequence of nodes v1,…,vk∈Vv_1,\dots, v_k \in Vv1,…,vk∈V with the property that each consecutive pair vi,vi+1v_i, v_{i+1}vi,vi+1 in ppp is connected by an edge ei∈Ee_i \in Eei∈E . The number of all such edges is called the length of the path. The distance or geodesic distance d(i,j)d(i,j)d(i,j) between two vertices iii and jjj in a graph is defined as the length of the shortest path between them. If no such path exists, we define d(i,j)=∞d(…
Average Distance and Diameter
The average distance in a graph is the arithmetic mean of the finite distances (i.e., shortest paths) between all pairs of vertices. The diameter of a graph is defined as the longest distance (i.e., the longest shortest path) between any pair of vertices for which a path exists.
Cycle and Eulerian Path
A path v1,…,vk v_1,\dots,v_kv1,…,vk with at least three edges is called a cycle if the first and the last vertices are the same, but otherwise all vertices are distinct. A path that traverses each edge exactly once is called an Eulerian Path.
Connectivity
An undirected graph GGG is called connected if there exists a path from every vertex to every other vertex. A directed graph GGG is called strongly connected if there is a directed path from every node to every other node. A directed graph GGG is called weakly connected if there is one path from each vertex to each other when ignoring the edges’ orientation.
Connected Component and Subgraph
A graph G′=(V,′E′) G'=(V,' E')G′=(V,′E′) is a subgraph of the graph G=(V,E)G=(V, E)G=(V,E) if its vertices V’V’V’ and its edges E’E’E’ are subsets of the vertices and edges of GGG , i.e., V’∈V V’ \in VV’∈V and E’∈EE’ \in EE’∈E . A connected component of an undirected graph G=(V,E)G=(V, E) G=(V,E) is a subgraph G’=(V’,E’)G’=(V’, E’)G’=(V’,E’) that is: Connected Maximal ( if you added any other node, it is no longer connected)
Strongly and weakly connected Components
In a directed graph two types of connected components are defined: strongly connected components (SCC) and weakly connected components (depending on wether they are strongly or weakly connected).
In- and Out-Component
In a directed graph the out-component of a specific vertex A is the set of vertices that are reachable via paths starting at AAA and including AAA . The in-component of a specific vertex A is the set of all vertices from which there is a directed path to AAA , including AAA itself.
Giant Component
Is a component that contains the vast majority of all nodes. Networks normally only have on giant component
Network Data Representation
Matrix Edgelist Graph
Types of networks
A full or complete network contains all entities of the network and the connections among them. All entities are treated equally. In practice, it is not always feasible (or particularly insightful) to analyse a full network. Instead, a partial network by selecting a subgraph of the full network is created. Also: Egocentric networks unimodal/multimodal networks Multiplex networks
Egocentric network
An egocentric network only includes individuals who are connected to a specified ego. More generally, an egocentric network can extend out any number of degrees from ego. Types: The basic 1-degree ego network consists of the ego and their alters. The 1.5-degree ego network extends the 1-degree network by including connections between all of the alters. The 2-degree ego network extends the 1.5-degree network by including all of the alters’ own alters (i.e., friends of friends), some of whom may…
Bipartite Networks
A two-mode or bipartite network is a multimodal network with exactly two types of vertices.
Multiplex network
Multiplex network: a network with multiple types of connections or edges. Could be represented by using edge labels For network analysis: network measures can usually not be applied to multiplex networks, so multiple types of edges are combined to get a single one
Centrality Indices
In a network some vertices or edges are more central or important than others l Intuitively clear, but hard to formalise and strongly dependent on the context. Classical Centrality Indices: Degree Centrality, Eigenvector Centrality, Closeness Centrality,Betweenness Centrality Web Centralities: Hubs and Authorities, PageRank
Degree Centrality (in-degree and out-degree)
Eigenvector Centrality
Closeness Centrality
Betweenness Centrality
Hubs and Authorities
suggested ranking procedure Authorities: prominent, highly endorsed answers to the query Hubs: high-value lists For each page p estimate its value as potential authority and as potential hub --> assign two numerical scores: auth(p) and hub(p) For values except for some rare cases (eigenvector centrality) k→∞ the normalized values converge to limiting
PageRank (with recursive formula)
Equilibrium Values of PageRank
Clique
A clique is a maximal subset of the vertices in a network such that every member of the set is connected by an edge to every other member (i.e., subset forms a complete graph).
K-Core
A k-core is a maximal subset of vertices such that each is connected to at least k others in the subset Important concept because the set of all k-cores in the network is easy to compute:
K-Component
A k-component is a maximal subset of vertices such that each is reachable from each of the others by at least k vertex-independent paths.
Vertex-independent
Two paths are said to be vertex-independent if they share none of the same vertices except the starting and ending vertex.
Triadic Closure
In many “real-world” networks, particularly in social networks, the fact that uuu is connected to vvv and vvv is connected to www makes it much more likely that uuu is connected to www as well.
Clustering Coefficient
The clustering coefficient reflects the probability that two randomly selected neighbours of a vertex are connected by an edge.
Reciprocity
In a directed graph, if there is an edge from vertex iii to vertex and jjj there is also an edge from j to i then we call the edge (i,j)(i, j)(i,j) reciprocated. The reciprocity rrr is defined as the fraction of edges that are reciprocated: r=smr = \frac{s}{m}r=ms Here, mmm denotes the total number of edges in the graph, and sss the number of reciprocated edges.
(local) Bridge, span
An edge in graph is called a bridge if the removal of the edge would increase the number of connected components. An edge is called a local bridge if its endpoints have no common neighbour. The span of an edge is the distance its endpoints would be from each other if the edge were deleted.
Strong ties, weak ties
strong ties ( sss ): stronger links, corresponding to friends weak ties ( www ): weaker links, corresponding to acquaintances
Strong Triadic Closure Property
We say that a node AAA violates the Strong Triadic Closure Property if it has strong ties to two other nodes BB B and CCC , and there is no edge at all (either a strong or weak tie) between BBB and CCC . We say that a node AAA satisfies the Strong Triadic Closure Property if it does not violate it.
Neighbourhood Overlap
∣N(A)∩N(B)∣∣N(A)∪N(B)∣−2\frac{|N(A)\cap N(B)|}{|N(A)\cup N(B)|-2}∣N(A)∪N(B)∣−2∣N(A)∩N(B)∣ for an edge (A,B)(A,B)(A,B) where N(A)N(A)N(A) denotes the set of all neighbors from vertex AAA . It is useful to identify "almost" local bridges in large networks. If the edge is a bridge, the overlap is 0, if it's an "almost" bridge, it's very small.
Community Structure
Division of the vertices of the network into groups within which the connections are dense, but between which they are sparser.
Girvan Newman Algorithm
Modularity
Modularity Q measures the quality of a particular division of the network by comparing the edge distribution of the division to a network were the edges are distributed randomly. Modularity around 1 indicates strong community structure, around 0 means not better than random.
Modularity maximization Algorithm
Signatures of Relational Analysis
Ideation Signature Focus: Individual Predicts: Which employees will come up with good ideas Influence Signature Focus: Individual Predicts: Which employees will change others’ behavior Efficiency Signature Focus: Team Predicts: Which teams will complete projects on time Innovation Signature Focus: Team Predicts: Which teams will innovate effectively Silo Signature Focus: Organization Predicts: Whether an organization is siloed Vulnerability Signature Focus: Organization Predicts: Which employee…
Homophily
Homophily is the principle that we tend to be similar to our friends.
Homophily Test
Immutable and mutable characteristics
Immutable characteristics: Tendency of people to form friendships with others who are like them is often termed selection Social environment already favours opportunities to form friendships with others like oneself With selection, the individual characteristics drive the formation of links. Mutable Characteristics: People may modify their behaviors to bring them more closely into alignment with the behaviors of their friends (Socialisation or social influence) With social influence, the existi…
Focal Closure
Tendency of two people to form a link when having a focus in common
Membership Closure
B takes part in a focus in which her friend A is already involved.
Structural Balance
Balance Theorem
purely local property
Weakly Balanced Networks
Complete graph is weakly balanced if there is no set of three nodes such that the edges among them consist of exactly two positive edges and one negative edge
Structural Balance in Non-Complete Networks
Two ways to define structural balance in arbitrary graphs: If it can be completed by adding edges to form a complete graph, that is balanced Divide the nodes into two sets XXX and YYY so that all edges inside XXX and inside YYY are positive and all edges between are negative Both definitions are equivalent
Small-World Effect
Phenomenon that in most networks the average distance between two vertices is surprisingly small Due to one giant component
Global Clustering Coefficient
Measures the density of triangles in the network C=3⋅(number of closed triangles)number of connected triplesC= \frac{3 \cdot (\text{number of closed triangles})}{\text{number of connected triples}}C=number of connected triples3⋅(number of closed triangles) where connected triple: Three vertices u,v,wu,v,wu,v,w with edges (u,v)(u,v)(u,v) and (v,w)(v, w)(v,w) . Edge (u,w)(u, w)(u,w) can be present or not Alternative definition: average of local clustering coefficients
Degree Distribution and Degree Sequence
Degree distribution: Frequency distribution of vertex degrees Degree sequence {k1,k2,...}\{k_1, k_2,...\}{k1,k2,...} also contains information about degree distribution ( kik_iki is degree of vertex iii )
Power Laws
Rich-get-Richer-Models
Also called winner takes it all or preferential attachment
80/20 Rule
Roughly 80% of xxx is owned/earned/... by 20% of people It is a power law distribution Known as Pareto principle
Network Model
Used to: Understand current structure Predict future behaviour Mathematical models for evolving networks developed for reasons: Model should show nature of development of real world network Should mathematically analyzable Should be well suited for computational purpose (Simulations)
Random Graph G(n,p)G(n,p)G(n,p) (Erdös-Rényi)
The probability of edges is fixed, not the number Each pair of nodes is connected with probability p Expected number of edges connected to one vertex is (n−1)p(n-1)p(n−1)p Expected number of edges in graph is: (n2)p\begin{pmatrix}n \\ 2 \end{pmatrix} p(n2)p The probability of a vertex vvv having degree kkk is binomial: P(deg(v)=k)=(n−1k)pk(1−p)n−1−k\mathbb{P}(\text{deg}(v)=k)=\begin{pmatrix}n-1 \\ k \end{pmatrix} p^k (1-p)^{n-1-k}P(deg(v)=k)=(n−1k)pk(1−p)n−1−k For large nnn this is a Poisson…
Small World Model (Watts-Strogatz)
abstract model with small average distance and high clustering coefficient
Barabási-Albert Model
Based on undirected network Uses two mechanisms: growth and preferential attachment: When deciding where to establish a link, a node prefers to attach to an existing node, that already has many connections
Processes on Networks
Network resilience (take a network, remove a fraction of its vertices -> how does it effect the network structure) Cascading failure (Failure of vertex causes redistribution of load to other vertices -> Load on them exceeds maximum capacity -> cascading failure) Epidemic processes on networks (spreading of diseases over networks) Dynamical systems on networks (spread of news and information/traffic and data on a network) Network search and network navigation (practical applications in context o…
Simple Diffusion
In each unit of time a vertex adopts a new behaviour of its neighbours with the same probability ppp
Threshold Model
Model for diffusion of a new behaviour through a network Assumes, that you benefit more of adopting a new behaviour if more of your neighbours adopt the new behaviour
Basic Cascade Model
Initial Situation: Everyone in network uses BBB as default behaviour Small set of initial adopters decide to use AAA Some of their neighbours decide to switch to AAA Depending on Network structure, number and position of initial adopters and threshold qqq (adopt value), this casues cascading behaviour so entire network uses AAA
Limitations of small world model
The degree distribution does not follow a power-law The number of vertices is fixed -> can not model growth process
Limitations of Random Graph
Degree distribution does not follow a power law Clustering coefficient is quite low No community structure Graph is undirected
Cluster