Community Common Definition: A community is a set of nodes among which the connections are relatively dense and strong or interactions are relatively frequent t A network has a community structure if the network can naturally be divided into groups of nodes with dense internal connections and sparse external connections e Community Detection(grouping, clustering) To find cohesive subgroups Applications Understanding interactions between people(or systems) Visualizing and navigating on large-scale networks Forming bases for other tasks such as data mining
Community ⸙ Common Definition: A community is a set of nodes among which the connections are relatively dense and strong or interactions are relatively frequent ⸙ A network has a community structure if the network can naturally be divided into groups of nodes with dense internal connections and sparse external connections ⸙ Community Detection (grouping, clustering) To find cohesive subgroups ⸙ Applications Understanding interactions between people (or systems) Visualizing and navigating on large-scale networks Forming bases for other tasks such as data mining …
Mathematic Expression Examples Definition Nodes in any two communities are Disjoint communities GraphG=g(v, E), the not overlap, community detection is to find the nc communities C={c1,C2,…,Cnc} I Otherwise Overlapping communities Nodes in communities cover all the nodes v in the network Communities in networks
Mathematic Expression Definition Examples Communities in networks Graph G = G(𝑉, 𝐸), the community detection is to find the 𝑛𝑐 communities ∁= {𝑐1, 𝑐2, … , 𝑐𝑛𝑐} Nodes in communities cover all the nodes 𝑉 in the network Nodes in any two communities are not overlap, Disjoint communities Otherwise, Overlapping communities
Community detection Many real networks have a natural community structure. and we want to discover this structure [Adamic Glance, 2005 For a large-scale network. how can we discover community structure in an automated way?
Community Detection Many real networks have a natural community structure, and we want to discover this structure For a large-scale network, how can we discover community structure in an automated way?
Methods and Algorithms 1)Minimum-cut method 2)Hierarchical clustering 3)GN algorithm 4)Clique-based methods 5)Modularity maximization 6)Information-based algorithms
Methods and Algorithms 1) Minimum-cut method 2) Hierarchical clustering 3) GN algorithm 4) Clique-based methods 5) Modularity maximization 6) Information-based algorithms ……
1)Minimum-Cut Method c One of the oldest algorithms for dividing networks into Example parts The network is divided into a pre- 2 determined number of groups, in 6 approximately the same size (balanced), chosen such that the number or cost(total weights)of edges between groups is minimized
3 1 1) Minimum-Cut Method The network is divided into a predetermined number of groups, in approximately the same size (“balanced”), chosen such that the number or cost (total weights) of edges between groups is minimized. Example One of the oldest algorithms for dividing networks into parts