UNIT 5: SOCIAL NETWORKS

I. FOUNDATIONS OF THE SOCIAL WEB

Emergence of the Social Web

The Social Web refers to the evolution of the World Wide Web from a static information repository to a dynamic, interactive, and user-generated content platform. Key milestones include:

• Web 1.0 (1990s): Read-only web (static HTML pages).

• Web 2.0 (Mid-2000s): Read-write web; rise of platforms enabling user interaction, collaboration, and content creation (e.g., blogs, wikis, early social networks like Friendster, MySpace).

• Web 3.0 (Present): Semantic web and decentralized web; focus on data interoperability, machine-readability, and user ownership (e.g., linked data, blockchain-based social networks).

[!TIP] Exam Focus: Be prepared to cite specific platforms (e.g., SixDegrees.com as first social network, Facebook, Twitter) and technologies (AJAX, APIs) that drove the Web 2.0 shift.

Types of Web-Based Networks

Web-based networks can be classified based on the nature of entities and relationships:

II. SOCIAL NETWORK ANALYSIS (SNA) CORE CONCEPTS

Importance and Applications of SNA

SNA provides a mathematical framework to study the structure and behavior of social systems. Its importance lies in:

• Identifying Key Actors: Finding influential individuals (via centrality).

• Understanding Information Flow: Tracking how information, behaviors, or innovations spread.

• Detecting Communities: Finding groups with dense internal connections.

• Analyzing Resilience: Assessing network robustness to node/edge removal.

• Applications: Marketing (viral campaigns), public health (disease transmission), cybersecurity (detecting botnets), organizational management.

Matrix Representation of Graphs

Graphs are represented using matrices for computational analysis.

1. Adjacency Matrix (A):

   • A square matrix where element $$\displaystyle a_{ij} = 1 $$ if a directed edge exists from node $i$ to node $j$, else $0$.

   • For undirected graphs, $A$ is symmetric ($$\displaystyle a_{ij} = a_{ji} $$).

   • Properties: The $k$-th power of $A$, $$\displaystyle A^k $$, gives the number of walks of length $k$ between nodes. The sum of row $i$ gives the out-degree of node $i$; sum of column $i$ gives the in-degree.

2. Incidence Matrix (B):

   • A rectangular matrix (nodes × edges). $$\displaystyle b_{ij} = 1 $$ if node $i$ is incident to edge $j$, else $0$.

   • For directed graphs, $$\displaystyle b_{ij} = +1 $$ if edge $j$ starts at node $i$, $-1$ if it ends at $i$, $0$ otherwise.

[!TIP] Common Pitfall: Do not confuse adjacency matrix (node-to-node) with incidence matrix (node-to-edge). Adjacency is used for path-counting and centrality calculations.

Centrality Measures

Quantify the "importance" or "influence" of a node.

\boxed{C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}}

Clustering

1. Clustering Coefficient (Local & Global):

   • Local $$\displaystyle C_v $$: Fraction of a node's neighbors that are connected to each other.

$$C_v = \frac{2 \times \text{Number of edges among } N_v \text{ neighbors}}{k_v(k_v - 1)}$$

    where $$\displaystyle k_v $$ is the degree of node $v$.

*   **Global $\bar{C}$:** Average of all local clustering coefficients. Measures the overall tendency of nodes to cluster.

2. Community Detection (Modularity):

   • Goal: Partition network into communities (modules) with dense internal connections and sparse external connections.

   • Modularity ($Q$): Measures the quality of a partition.

$$Q = \frac{1}{2m} \sum_{ij} \left[ A_{ij} - \frac{k_i k_j}{2m} \right] \delta(c_i, c_j)$$

    where:

    *   $$\displaystyle A_{ij} $$: adjacency matrix element.

    *   $$\displaystyle k_i, k_j $$: degrees of nodes $i,j$.

    *   $m$: total number of edges.

    *   $$\displaystyle \delta(c_i, c_j) = 1 $$ if nodes $i,j$ are in same community, else $0$.

*   **Interpretation:** $Q$ compares the actual edge density within communities to the expected density in a random network with the same degree sequence. **Higher $Q$ (~0.3-0.7) indicates a strong community structure.**

III. SEMANTIC WEB & ONTOLOGIES FOR SOCIAL DATA

Resource Description Framework (RDF) & RDF Schema

• RDF Data Model: The fundamental data model for the Semantic Web. Represents information as triples (Subject, Predicate, Object).

  • Subject: Resource being described.

  • Predicate: Property or relationship.

  • Object: Value of the property (another resource or a literal).

  • Example: (Alice, knows, Bob).

  • Data is stored as a directed labeled graph.

• RDF Schema (RDFS): A lightweight ontology language for RDF.

  • Defines classes (e.g., Person, Organization) and properties (e.g., knows, worksFor).

  • Allows subclass (rdfs:subClassOf) and subproperty (rdfs:subPropertyOf) relationships.

  • Provides domain (class of subjects) and range (class of objects) constraints for properties.

  • Limitation: Limited expressiveness (e.g., cannot state that a property is transitive or that two classes are disjoint).

Web Ontology Language (OWL)

OWL is a more expressive ontology language built on RDF(S).

• Unique Features & Expressiveness:

  • Cardinality Restrictions: Specify exact number of relationships (e.g., hasSpouse exactly 1).

  • Property Characteristics: Declare properties as transitive (ancestorOf), symmetric (marriedTo), functional (hasMother), or inverseOf another property (hasParent is inverse of hasChild).

  • Class Expressions: Define complex classes using intersections (and), unions (or), complements (not).

  • Equivalence & Disjointness: State that two classes are equivalent or mutually disjoint.

  • Open World Assumption: Unlike databases, absence of information is not assumed false. New facts can always be added.

• Comparison with RDFS:

  | Feature | RDFS | OWL | | :--- | :--- | :--- | | Expressiveness | Low (taxonomic hierarchies) | High (full description logic) | | Cardinality | No | Yes | | Property Chains | No | Yes (via owl:propertyChainAxiom) | | Automated Reasoning | Limited (subclass/subproperty) | Extensive (consistency, classification, instance checking) | | Complexity | Polynomial | NP-Complete (for full OWL) |

FOAF (Friend of a Friend)

• Foundation: An RDF-based vocabulary (ontology) for describing people, their relationships, and activities on the Social Web.

• Core Concepts:

  • foaf:Person: The primary class representing an individual.

  • Key Properties:

    • foaf:name, foaf:mbox (email), foaf:homepage.

    • foaf:knows (social connection), foaf:member (group membership).

    • foaf:depicts (image of person).

  • Social Graph Construction: By linking foaf:knows statements, a decentralized social graph can be built across different websites.

• Significance: Provides a standardized, machine-readable way to represent social profiles and relationships, enabling data portability and interoperability between social platforms.

IV. COMMUNITY DETECTION & NETWORK DYNAMICS

Definitions of a Community

A "community" (or module/cluster) lacks a single universal definition. Main approaches:

1. Local Definition (Vertex-Centric): A community is a set of nodes that are more densely connected internally than with the rest of the network.

   • Example: A clique (complete subgraph) is a strong local community.

2. Global Definition: A community is a subgraph whose internal edge density is significantly higher than the average density of the whole network.

   • Formal: For a subgraph $S$, density$(S) \gg$ density$(G)$.

3. Definitions Based on Vertex Participation:

   • Structural: Based on graph topology (e.g., high clustering coefficient, participation coefficient).

   • Spectral: Based on eigenvectors of matrices (e.g., using Laplacian eigenvectors).

   • Dynamic: Based on flow or random walks (e.g., communities as basins of attraction for random walkers).

[!TIP] Exam Key: Be able to contrast local vs. global definitions. Local is intuitive but may find overlapping communities; global gives a single partition but may miss small dense groups.

Extracting Community Evolution

To study how communities form, dissolve, merge, or split over time from a series of web archives (time-stamped snapshots):

1. Track Individual Communities: Detect communities in each snapshot $t$ and $t+1$, then match them using Jaccard similarity of node sets.

$$J(S_t, S_{t+1}) = \frac{|S_t \cap S_{t+1}|}{|S_t \cup S_{t+1}|}$$

2. Evolution Metrics:

   • Birth/Death: Community appears/disappears.

   • Growth/Shrinkage: Change in size (number of nodes).

   • Merge/Split: Two communities combine or one divides.

   • Stability: Average Jaccard similarity of a community across consecutive snapshots.

   • Core-Periphery Evolution: Tracking the stability of core nodes vs. turnover of peripheral nodes.

Network Reduction Techniques

Simplify large, dense networks for visualization and analysis while preserving key structural properties.

1. k-Core Decomposition: Iteratively remove nodes with degree less than $k$. The remaining subgraph is the $k$-core. Reveals the dense core of the network.

2. k-Shell Decomposition: Further refines $k$-core by peeling layers. Nodes in higher shells are more central.

3. Community-Based Reduction: Replace each detected community with a super-node or meta-node. Edges between super-nodes represent inter-community connections.

4. Spanning Tree Extraction: Keep only edges that form a spanning tree (minimally connected) or a minimum spanning tree (weighted).

5. Backbone Extraction (Disparity Filter): For weighted networks, remove edges whose weight is not statistically significant given the degrees of the nodes they connect.

V. APPLICATIONS & ENABLING HUMAN EXPERIENCES

Social Networks as an Enabler

Social networks facilitate new human experiences by:

• Persistence: Conversations and connections are stored indefinitely.

• Searchability: Easy to find people and information.

• Replicability: Content can be easily copied and shared.

• Invisible Audiences: The potential audience is often unknown to the poster.

• Social Transparency: Blurring of public/private boundaries.

• New Forms of Identity: Curated digital selves, multiple personas.

• Collective Intelligence: Crowdsourcing, wisdom of crowds.

Reality Mining

• Concept: The collection and analysis of sensor data (primarily from mobile phones) to infer real-world human behavior, relationships, and patterns.

• Data Collection: Call logs, SMS, Bluetooth scans (proximity), GPS locations, app usage, accelerometer data.

• Applications:

  • Social Network Inference: Detecting friendships from proximity and communication patterns.

  • Urban Planning: Understanding human mobility patterns.

  • Public Health: Modeling disease spread.

  • Context-Aware Services: Providing location-based recommendations.

  • Productivity Analysis: inferring workplace interactions.

Context Awareness

• In Social/Computational Contexts: Systems that adapt their behavior based on information about the user's environment, situation, or activity.

• How Achieved: By integrating data from multiple sensors (location, time, device state, social context from SNA).

• Uses:

  • Social Context: "Are friends nearby?" (e.g., Foursquare, Facebook Places).

  • Physical Context: Location-based services (navigation, local search).

  • Activity Context: Automatically setting phone mode (silent in meeting), suggesting relevant content.

  • Socially-Aware Applications: Modifying information sharing based on who is physically present.

VI. PRIVACY, SECURITY & ATTACK SPECTRUM

Privacy Issues in Online Social Networks (OSNs)

• Data Harvesting: Unauthorized collection of user data (profiles, posts, connections) by third parties (e.g., via APIs, scraping).

• Profiling & Inference Attacks: Aggregating seemingly harmless data to infer sensitive attributes (political views, health status, sexual orientation). Social inference is a major threat.

• Lack of Control: Difficulty in managing who sees past posts (context collapse), data once shared is hard to retract.

• Re-identification: Anonymized datasets can be re-linked to individuals using auxiliary information.

• Surveillance: Government or corporate monitoring of social interactions.

Attack Spectrum in OSNs

Censorship Attacks

• Methods: Government or institutional blocking of access to OSNs or specific content (IP blocking, DNS tampering, keyword filtering, throttling).

• Impact on Social Networks:

  • Disrupts communication and organization (e.g., during protests).

  • Creates information vacuums and hinders free expression.

  • Forces users to adopt circumvention tools (VPNs, Tor), which may have usability and security trade-offs.

  • Challenges the global, open nature of the web.

Challenges for Decentralized Online Social Networks (DOSNs)

DOSNs (e.g., based on ActivityPub, Solid) aim to give users control over their data.

• Technical Challenges: Scalability, data synchronization across servers, complex identity management, ensuring interoperability between different DOSN software.

• Adoption Challenges: Network effect problem (users stay on dominant centralized platforms like Facebook), steep learning curve, lack of critical mass of friends.

• Privacy & Security Challenges: While data is decentralized, metadata (who connects to whom, when) can still be leaked. Server operators (even if user-controlled) can see activity. Key management for end-users is difficult.

VII. SUPPORTING TECHNOLOGIES & PROTOCOLS (Contextual)

Email Groups

• As Early Web-Based Network: Mailing lists (e.g., Google Groups, Listserv) are a precursor to modern social networks.

• Characteristics:

  • Asynchronous Communication: Messages are stored and delivered later.

  • One-to-Many Broadcast: A single post reaches all subscribers.

  • Persistent Archive: All messages are stored, creating a searchable knowledge base.

  • Membership-Based: Access controlled by subscription/moderation.

  • Tight-Knit Communities: Often formed around specific interests or organizations, fostering deep discussions.

• Limitation: Primarily text-based, less rich media and interactive features compared to modern platforms.

RSS Feeds

• Role: Really Simple Syndication (RSS) is a web feed format for publishing frequently updated content (blogs, news, podcasts).

• In Network Formation:

  • Push Model: Allows users to subscribe to content sources without visiting the site.

  • Aggregation: Feed readers (aggregators) collect updates from multiple RSS feeds, creating a personalized information network.

  • Decentralized Curation: Users build their own news stream by choosing sources, bypassing algorithmic feeds of centralized platforms.

  • Enables Niche Communities: Supports long-tail content and direct publisher-audience relationships.

• Decline: Largely superseded by social media algorithms and closed APIs, but remains important for open web principles.

END OF UNIT 5 NOTES