Cohesive Subgraphs Cohesive subgroups are subsets of actors among whom there are relatively strong, direct, intense, frequent or positive ties Different cohesive subgroups are formed according to different cohesive relations, which are further specified by application needs Social networks can be represented as graphs, such that We formalize cohesive subgroups as cohesive subgraphs Correspondingly, the problem of finding cohesive subgraphs on graphs are referred to as Cohesive subgraph search
Cohesive Subgraphs 16 • Cohesive subgroups are subsets of actors among whom there are relatively strong, direct, intense, frequent or positive ties [1] . – Different cohesive subgroups are formed according to different cohesive relations, which are further specified by application needs. • Social networks can be represented as graphs, such that we formalize cohesive subgroups as cohesive subgraphs. – Correspondingly, the problem of finding cohesive subgraphs on graphs are referred to as Cohesive subgraph search
Cohesive Subgraphs Various cohesive subgraphs(clique, n-clan, k-plex, k-core) ne: Castellani n nll: Peruzzi 15: Strozzi Maximal clique: a maximal clique ●n: Barbados n4: Eischen is a maximal complete subgraph Ridolfi M ain issues n1]: Tomabuorn 114: salviati no: Medic Cliques can overlap P n]: Guadagni Too many or too few cliques n2: Albizzi]: Acciaiuohi emerge n&: Lamberteschi The problem is NP-complete ns: Canon “ Padgett' s Florentine families
Cohesive Subgraphs 17 • Various cohesive subgraphs (clique, n-clan, k-plex, k-core) Maximal clique: a maximal clique is a maximal complete subgraph. “Padgett's Florentine Families” • Main issues: – Cliques can overlap – Too many or too few cliques emerge – The problem is NP-complete
Cohesive Subgraphs Various cohesive subgraphs(clique, n-clan, k-plex, k-core) n: Castellani n nll: Peruzzi N-clique: an n-clique is a maximal subgraph in which the n1s: Strom Qn]: Barbados largest distance between any two n4: Eischen nodes is no greater than n n13: Ridolfi N-clan: an n-clan is an n-clique in n16:Tornabuoni 114: salviati which the diameter is no greater n n]: Guadagni no: Pazi than n K-core a k-core is a maximal n2: Albizzi]: Acciaiuohi n&: Lamberteschi subgraph in which the nodal degree of each node Is no ns: Canon smaller than k Padgett's Florentine Families The cohesive relations are gradually looser
Cohesive Subgraphs 18 N-clique: an n-clique is a maximal subgraph in which the largest distance between any two nodes is no greater than n. N-clan: an n-clan is an n-clique in which the diameter is no greater than n. K-core: a k-core is a maximal subgraph in which the nodal degree of each node is no smaller than k. “Padgett's Florentine Families” The cohesive relations are gradually looser • Various cohesive subgraphs (clique, n-clan, k-plex, k-core)