Network Science Co-authorship Quiz

Community Structure in Networks

• CS224W: Analysis of Networks course taught by Jure Leskovec at Stanford University
• Course website: http://cs224w.stanford.edu

Roles and Communities: Example

• Roles in networks are structural roles of nodes. Examples include connector nodes, bridge nodes, etc.
• Communities are clusters/groups of nodes well-connected to each other.
• Roles and communities are complementary concepts.
• Examples of roles include centers of stars and members of cliques, as well as peripheral nodes.

Plan for Today

• The topics for today's class include structural role discovery in networks and community detection via modularity optimization.

Structural Roles in Networks

• Roles are "functions" in a network, such as species roles in an ecosystem, or individual roles in companies, etc.
• Roles are measured by structural behaviors (e.g., centers of stars, members of cliques, and peripheral nodes).

What are Roles?

• Roles of nodes are their functions in a network.
• Roles can be observed in ecosystems and companies.
• Roles are measured by analyzing structural behaviors, like how central a node is or if it connects groups of nodes.

Example of Roles

• Examples of roles in a network include centers of stars, members of cliques, and peripheral nodes. A specific example is the co-authorship network.

Roles versus Groups in Networks

• Roles are collections of nodes with similar network positions. Roles are based on the similarity of ties among subsets of nodes.
• Communities are cohesive subgroups, formed by adjacency, proximity or reachability of nodes.

Roles and Communities

• Roles are groups of nodes with similar structural properties in a network.
• Communities are groups of well-connected nodes in a network.
• Roles and communities complement each other.

Roles: More Formally

• Structural equivalence: Nodes are structurally equivalent if they have the same relationships to all other nodes. (Lorrain & White, 1971)
• Structurally equivalent nodes tend to have similar characteristics.

Structural Equivalence: Example

• Nodes are structurally equivalent if they have the same relationships to all other nodes in the network.
• Example adjacency matrix given for a specific case.

Discovering Structural Roles in Networks

• RoIX is a method for automatically discovering structural roles in networks.
• It's an unsupervised learning approach, doesn't require pre-existing knowledge and scales linearly with the number of edges.

RoIX: Approach Overview

• RoIX takes the adjacency matrix as input.
• Recursive feature extraction turns network connectivity into structural features (eg, degree, mean weight).
• Role extraction forms the node role matrix and role feature matrix as output

Recursive Feature Extraction

• Recursive feature extraction transforms network connectivity into structural features.
• Neighborhood features describe a node's connectivity pattern.
• Recursive features describe the types of nodes a node is connected to.
• Different neighborhood features are calculated recursively (eg, degree, mean weight, local ego-network).

Why Are Roles Important?

• Roles in networks are helpful for various tasks including identifying similar individuals, finding outliers with unusual behaviors, or following changes in network behavior. They are also helpful for identifying individuals in a new network or making predictions about one network using knowledge from another, or comparing networks.

Application: Structural Similarity

• The task is clustering nodes based on their structural similarity.
• Examples of networks are co-authorship and political co-purchasing networks.
• RoIX is used to assign each node a distribution over the set of discovered structural roles, then comparing these distributions to determine node similarity.

Structural Sim: Co-authorship Net

• Using RoIX, nodes are colored by their primary role (tightly knit, bridge, main-stream, or pathy). A heatmap shows node role affinity.

Community Structure in Networks

• This topic discusses the concept of communities in networks.

Roles and Communities: Example (repeated)

• This section provides examples of role and community structures in networks.

Networks & Communities

• Networks are often viewed as collections of tightly-connected groups of nodes, possibly representing communities.

Networks: Flow of Information

• This section focuses on information flow patterns through networks, considering structurally distinct node roles and the types of links involved: short vs. long.
• Using real example data and Granovetter's research on job search indicates that it's more likely to receive helpful information from acquaintances than close friends.

Granovetter's Answer

• Granovetter's research gives two perspectives on friendships: structural (how friendships spread over the network), and interpersonal (the strength of relationships, strong vs. weak).
• In his study regarding structural role, he proposed the concept of triadic closure where two people in a network with a common connections are more likely to become friends.

Granovetter's Explanation

• Granovetter connects social roles with network structure
• Structurally embedded edges (strong connections) are socially strong, while long-range edges (weak connections) span diverse parts of the network and provide broader information access.

Triadic Closure

• Triadic closure is a structural role that describes the pattern of high clustering coefficients where if B and C have a common friend A, it is more likely that B and C become friends.

Tie strength in real data

• In real networks (e.g., internet, phone calls), Granovetter's tie strength concepts have been tested using large network data sets.

Neighborhood Overlap

• Edge overlap is a measure of the shared neighbors between two nodes.

Phones: Edge Overlap vs. Strength

• High-usage phone calls have higher neighborhood overlap.

Real Network, Real Tie Strengths

• Strong ties in mobile call graphs are more embedded.

Real Net, Permuted Tie Strengths

• The same network, with randomly shuffled strengths, shows a different result.

Link Removal by Strength

• Removing links by decreasing strength order reveals how the removal of strong links disconnects the network sooner.

Link Removal by Overlap

• Removing links starting with low overlap to high sequentially, disconnects the network sooner.

Conceptual Picture of Networks

• Granovetter's theory leads to seeing networks as having strong and weak ties that are structured differently.

Network Communities

• Communities are sets of densely connected nodes in a network.

Finding Network Communities

• Automatic identification of densely connected groups (communities/clusters/modules) is the topic.

Social Network Data

• This section focuses on data from Zachary's Karate club network, illustrating a case where conflicts in a group lead to partitions, akin to a minimum cut in a network graph.

Micro-Markets in Sponsored Search

• Micro-markets in sponsored search algorithms are detected by partitioning web query-advertiser networks.

NCAA Football Network

• There is a discussion of how the connections between NCAA football teams (nodes) related to games played (edges), can be depicted as an undirected network representation.

NCAA Football Network (repeated)

• This shows how NCAA conferences (e.g., Mid American, Atlantic Coast, SEC, etc.) are represented in a network.

Facebook Ego-network

• This shows how Facebook ego-networks of users and their friends can be seen as a study on social communities.

Facebook Ego-network (repeated)

• This provides different examples of social communities (e.g., high school, Stanford) in a Facebook ego-network in graph form.

Protein-Protein Interactions

• Network analysis used for identifying functional modules in protein-protein interaction networks is described.

Protein-Protein Interactions (repeated)

• Functional modules in protein-protein interaction networks are highlighted.

Network Communities

• Communities are sets of tightly connected nodes in networks.
• Modularity Q is a measure of how well a network is divided into communities.
• A null model is needed to calculate expected values between nodes.

Null Model: Configuration Model

• A null model, in particular the configuration model, is used to determine what the expected number of edges would be between nodes in a network, accounting for the degree distribution. This model is used to compute the expected edge value between specific pairs of nodes.

Modularity

• Modularity (Q) is a measure of how well nodes are divided in communities within a network.
• Values range from -1 to 1, with higher values indicating stronger community structure.

Recap: Modularity

• Modularity (Q) is a measure of the degree to which nodes are well-clustered into communities.
• It is computed using a formula that has an indicator function
• Q values range from -1 to 1 and it is desirable that the Q value is large (approaching 1).

Louvain Modularity

• This section discusses the Louvain modularity concept.

Louvain Algorithm

• The Louvain algorithm is a greedy algorithm for community detection in networks, characterized by O(n log n) time complexity, optimized for weighed and hierarchical partitions within large graphs.

Louvain Algorithm: At High Level

• The Louvain Algorithm uses two phases (maximizing modularity) to determine communities.
• Phase 1 involves optimizing by considering only the local community changes.
• In Phase 2, the identified communities are aggregated.

Louvain: 1st phase (partitioning)

• The algorithm initially places each node into a distinct community. Then it iteratively determines if a node should be moved to another community based on which neighboring community maximizes community modularity.
• The algorithm runs till it finds no more improvements to the modularity from further moves.

Louvain: Modularity Gain

• The Modularity Gain (ΔQ) calculation determines whether to move a node to a different community.
• It's a formula taking into account interactions (i.e., links) between and within communities.

Louvain: 2nd phase (restructuring)

• The partitioning steps are applied to the super nodes, to create an aggregated network, whose edges between are defined by the summed edge weights between corresponding nodes in the partitions..
• The loop will continue until the community configuration (in the sense of the super nodes) stops changing.

Louvain Algorithm (repeated)

• This section gives a visual example of the Louvain algorithm.

Belgian Mobile phone network

• A network of Belgian mobile phone calls shows how French and Dutch speakers cluster into separate communities in a telephone usage graph.

Test your knowledge of network visualization and node representations in the Network Science Co-authorship Graph. This quiz covers various aspects, including color representation, node types, and role discovery within the network. Challenge yourself and explore the intricacies of network structures!