Algorytmy wykrywania społeczności

Welcome! In this lesson, we'll explore Community Detection Algorithms. These powerful tools help us find hidden groups or 'communities' within a graph.

Imagine a social network: friends form groups. These algorithms help identify such groups automatically.

A community in a graph is a set of nodes that are more densely connected to each other than to nodes outside the set.

• Think of it as a 'clique' or a 'cluster'.
• Nodes within a community often share common characteristics or interests.

Community detection is incredibly useful for understanding complex systems. Here are some applications:

• Social Networks: Finding friend groups or interest groups.
• Biology: Identifying protein families or gene clusters.
• Marketing: Segmenting customers with similar buying habits.
• Fraud Detection: Spotting networks of suspicious actors.

One of the simplest forms of community detection is finding Connected Components. A connected component is a subgraph where:

• Every node can be reached from every other node within that subgraph.
• There are no connections to any nodes outside that subgraph.

It's like finding entirely separate islands in a network.

Consider a graph representing different projects. If Project A has tasks and people, and Project B has its own tasks and people with no overlap, then Project A and Project B are two separate connected components.

They are distinct groups with no direct interaction.

Let's create a small graph to visualize two potential communities. Run this Cypher code to add some nodes and relationships.

After running the previous code, you'll see two distinct groups:

• Alice, Bob, and Charlie are all friends with each other.
• Xavier, Yara, and Zoe are all friends with each other.

There are no relationships between Alice's group and Xavier's group. These are two clear connected components, representing two communities.

Beyond simple connected components, algorithms like Label Propagation can find more nuanced communities. This algorithm works by:

1. Assigning a unique label to each node.
2. Nodes then adopt the label of the majority of their neighbors.
3. This process repeats until labels stabilize, forming communities.

It's like a rumor spreading through a network, where groups eventually share the same 'rumor' or label.

You've learned about Community Detection Algorithms, tools for finding natural groupings in graphs.

• We defined a community as a set of densely connected nodes.
• We explored Connected Components as a simple form of community.
• We briefly introduced Label Propagation as a more dynamic method.

These algorithms are key to understanding the structure and dynamics of complex networks.