Cohesive Subgraphs
COMP9312_22T2
Census date
Copyright By PowCoder代写 加微信 powcoder
26 Jun 2022, 11:59pm
Assignment 1 Due
24 Jun 2022, 9:00 pm
Guest Lecture on Monday Week 5
– Basic Concepts
– Applications
– Models and Algorithms
Community structure in graphs
Community structure: a cohesive group of nodes that are connected “more densely” to each other than to the nodes in other communities
– Within-group (intra-group) edges. High density
– Between-group (inter-group) edges.
Low density
Community structures are quite common in real networks.
Finding Communities
Who tend to work together
Co-author network
Information Retrieval
Machine learning
Q.Mei, D.Cai, D.Zhang, and C.Zhai, Topic Modeling with Hitting Time, WWW 2008
Data Mining
Finding Communities (Facebook or Twitter)
[McAuley, Leskovec: Discovering social circles in ego networks, 2012]
How to measure group cohesion?
q Mutuality of ties
– everybody in the group knows everybody else (clique)
q frequency of ties among members
– everybody in the group has links to at least k others in the group
q Others: density, quasi-clique, k-truss, k-edge connected component, etc.
Cohesive Subgraphs
In some models, a value 𝑘 can be used to capture the cohesiveness of the subgraph. For example, 𝑘-core is a maximal subgraph in which each vertex has at least k neighbors in the subgraph.
Application Summary
• NetworkModelingandAnalysis
• NetworkVisualization
• ReasoningtheCollapseofaNetwork • DiscoveringInfluentialNodes
• CommunityDiscovery
• AnomalyDetection
• ProteinFunctionPrediction
Application – Community Discovery
Social networks: persistent community search [ICDE 2018], spatial community search [ICDE 2018], attributed community detection [VLDB 2017] [VLDB 2017] [VLDB 2018] , influential community search [VLDB 2015]
A geo-social network Communities in Gowalla
Application – Network Modeling and Analysis
Complex networks: pattern and anomaly analysis using k-core analysis [ICDM 2016] [KAIS 2018]
Application – Network Modeling and Analysis
Social networks: modeling engagement dynamics in social graphs [CIKM 2013] [Social Networks 1983]
Application – Discovering Influential Nodes
The most effective spreaders are located in the core of the network, fairly independent of their degree. Influence of the infection probability beta on
the spreading efficiency M of nodes, grouped according to their k-shell values [Nature Physics 2010]
Application – Reasoning the Evolvement of a Social Network
Friendster network: revealing the mechanism of collapse [SNAM 2017] [COSN 2013]
Application – Fraud Detection
User-item networks:
Challenges:
• Billions of buyers and productions, 10+ billions of transactions
• Dynamic data
Solution:Efficient biclique detection on bipartite graph
Outcome: Significantly increase the recall by 40% in double 11 festival in 2017
Lyu B, , , et al. Maximum Biclique Search at Billion Scale[J]. Proc. VLDB Endow., 2020, 13(9): 1359-1372. [Best paper runner-up award in VLDB 2020]
Application –Group Recommendation
Customer-movie network:
, Li H, , et al. Efficient fault-tolerant group recommendation using alpha-beta-core[C] CIKM
Liu B, , , et al. Efficient (α, β)-core computation: An index-based approach[C], CIKM. 2019: 1130-1141.
Application – Team Formation
Author-paper networks: analyzing the relationships between groups of collaborators in the same institution
Sarıyüce A E, Pinar A. Peeling bipartite networks for dense subgraph discovery[C]//Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining. 2018: 504-512.
More Applications
• Graph clustering
Giatsidis, Christos, et al. “Corecluster: A degeneracy based graph clustering
framework.” AAAI. 2014.
• Graph similarity
Nikolentzos, Giannis, et al. “A Degeneracy Framework for Graph Similarity.” IJCAI. 2018.
• Community evaluation
Giatsidis, Christos, Dimitrios M. Thilikos, and . “Evaluating
cooperation in communities with the k-core structure.” ASONAM, 2011.
• Influence maximization
Elsharkawy, Sarah, et al. “Effectiveness of the k-core nodes as seeds for influence
maximisation in dynamic cascades.” International Journal of Computers 2 (2017).
• Graph generating
Baur, Michael, et al. “Generating graphs with predefined k-core structure.” Proceedings of the European Conference of Complex Systems. 2007.
Degree-based Models: K-Core and its Variants
K-core is a maximal connected subgraph in which each vertex has at least k neighbors in the subgraph
Erdős, Paul, and András Hajnal. “On chromatic number of graphs and set-systems.” Hungarica 17.1-2 (1966): 61-99.
Graph Degeneracy (𝑘!”#)
The largest k such that the k-core is not empty, which is also called the degeneracy.
Computing k-Core
Iteratively remove every vertex whose degree is less than k.
Computing k-Core
Iteratively remove every vertex whose degree is less than k.
Computing k-Core
Iteratively remove every vertex whose degree is less than k.
Computing k-Core
Iteratively remove every vertex whose degree is less than k.
Example: Online k-core computation
Iteratively remove every vertex whose degree is less than k.
This table lists the status of the vertices:
Find 3-core in this graph:
Example: Online k-core computation
Iteratively remove every vertex whose degree is less than k.
deg(v1)=1, deg(v9)=2, deg(v10)=1.
The degree of vertex 1, 9, 10 are smaller than 3, so we need to delete them.
Find 3-core in this graph:
Example: Online k-core computation
Iteratively remove every vertex whose degree is less than k.
deg(v2)=2, deg(v8)=2.
The degree of vertex 2, 8 is smaller than 3, so we need to delete them.
Find 3-core in this graph:
Example: Online k-core computation
Iteratively remove every vertex whose degree is less than k.
deg(v3)=2.
The degree of vertex 3 is smaller than 3, so we need to delete it.
Find 3-core in this graph:
Example: Online k-core computation
Iteratively remove every vertex whose degree is less than k.
The degree of all vertices is greater than 3, so the iteration is end. Then we get the result of 3-core.
Find 3-core in this graph:
Core Number Core number of a vertex 𝑣:
𝑘𝑣 =thelargestksuchthatthek-corecontains𝑣
Core Decomposition
Compute the core number of every vertex.
Note: If we store the core number of every vertex offline, given a graph G and a parameter k, all the vertices in the k-core (denoted as Ck(V, E)) of G can be returned in O(|V(Ck)|) time.
Tips: Store the vertices in decreasing order of their core numbers.
Core Decomposition (Cont.)
How to identify different groups?
There are two 3-cores in the example graph.
Core Decomposition: Methods
Global-view: peel low-degree vertices iteratively from the whole graph (which we introduce here).
Local-view: update the upper bound of core number for each vertex until converge.
Core Decomposition: Global-view (Peeling)
For each unvisited vertex u with the lowest degree in G
assign core(u) as degree(u); mark u as visited;
decrease the degree of its unvisited neighbors with higher degree than u by 1;
Core Decomposition: Global-view (Peeling)
For each unvisited vertex u with the lowest degree in G
assign core(u) as degree(u); mark u as visited;
decrease the degree of its unvisited neighbors with higher degree than u by 1;
Core Decomposition: Global-view (Peeling)
For each unvisited vertex u with the lowest degree in G
assign core(u) as degree(u); mark u as visited;
decrease the degree of its unvisited neighbors with higher degree than u by 1;
Core Decomposition: Global-view (Peeling)
For each unvisited vertex u with the lowest degree in G
assign core(u) as degree(u); mark u as visited;
decrease the degree of its unvisited neighbors with higher degree than u by 1;
Core Decomposition: Global-view (Peeling)
For each unvisited vertex u with the lowest degree in G
assign core(u) as degree(u); mark u as visited;
decrease the degree of its unvisited neighbors with higher degree than u by 1;
Core Decomposition: Global-view (Peeling)
For each unvisited vertex u with the lowest degree in G
assign core(u) as degree(u); mark u as visited;
decrease the degree of its unvisited neighbors with higher degree than u by 1;
Core Decomposition: Global-view (Peeling)
For each unvisited vertex u with the lowest degree in G
assign core(u) as degree(u); mark u as visited;
decrease the degree of its unvisited neighbors with higher degree than u by 1;
Core Decomposition: Global-view (Peeling)
For each unvisited vertex u with the lowest degree in G
assign core(u) as degree(u); mark u as visited;
decrease the degree of its unvisited neighbors with higher degree than u by 1;
Example: O(𝑛!) Algorithm for Core Decomposition A
Iterate over all the vertices. For a deleting vertex v, if the degree of its unvisited neighbor u is greater than the degree of v, then decrease the degree of u by one.
Example: O(𝑛!) Algorithm for Core Decomposition Start from the vertex A, A’s neighbor is B.
degree[B]>degree[A],
then degree[B]←degree[B]-1, degree[B]=2.
Example: O(𝑛!) Algorithm for Core Decomposition The next vertex is B, B’s unvisited neighbors are C and D.
degree[C]>degree[B],
then degree[C] ← degree[C]-1, degree[C]=3. degree[D]>degree[B],
then degree[D] ← degree[D]-1, degree[D]=2.
Example: O(𝑛!) Algorithm for Core Decomposition
The next vertex with the smallest degree is D,
D’s unvisited neighbors are C and G.
degree[C]>degree[D],
then degree[C] ← degree[C]-1, degree[C]=2. degree[G]>degree[D],
then degree[G] ← degree[G]-1, degree[G]=3.
Example: O(𝑛!) Algorithm for Core Decomposition The next vertex with the smallest degree is C,
C’s unvisited neighbor is E.
degree[E]=degree[C], then nothing would be changed.
degree[F]>degree[C],
then degree[F] ← degree[F]-1, degree[F]=4.
Example: O(𝑛!) Algorithm for Core Decomposition
The next vertex with the smallest degree is E,
E’s unvisited neighbor is F.
degree[F]>degree[E],
then degree[F] ← degree[F]-1, degree[F]=3.
Example: O(𝑛!) Algorithm for Core Decomposition The next vertex with the smallest degree is G,
G’s unvisited neighbors are F, H and I.
degree[H]=degree[G], degree[I]=degree[G], degree[F]=degree[G], then nothing would be changed.
Example: O(𝑛!) Algorithm for Core Decomposition
The next vertex with the smallest degree is F,
F’s unvisited neighbors are H and I.
degree[H]=degree[F], degree[I]=degree[F], then nothing would be changed.
Example: O(𝑛!) Algorithm for Core Decomposition
The next vertex with the smallest degree is H, H’s unvisited neighbor is I.
degree[I]=degree[H], then nothing would be changed.
Example: O(𝑛!) Algorithm for Core Decomposition A
The decomposition process is complete.
Quick exercise
Could you tell me the core number of each vertex?
Example: O(𝑛!) Algorithm for Core Decomposition The time complexity of the whole process is O(n2+m) = O(n2).
Need to get the vertex with minimum degree in each iteration: Using heap (priority queue): O(m*log(n))
Using Fabonacci heap: O(m+n*log(n)) Any better solution?
Core Decomposition using Doubly Linked List
For each degree d, store all vertices with degree d using a doubly linked list (DLL) When the degree of a vertex u decreases, move u from old DLL to a new DLL.
Time complexity: O(m)
Drawback: cannot fully utilize CPU cache~
Core Decomposition using Flat Array
In order to achieve the time complexity of O(m), we first sort all vertices according to their degree.
Iterate over all the vertices. If the degree of neighbouring vertex u of vertex v is greater than the degree of v, decrease the degree of u by 1. Then, for the line 7, swap the positions of u and the first vertex with the same degree as u’s original degree. Because we use the bin sort, the time complexity of reorder the array is O(n). Thus, the total time complexity for core decomposition is O(m).
Core Decomposition using Flat Array
Loop according to the order of degrees in the table, start from the vertex A with the minimum degree.
degree[B]>degree[A],
then degree[B] ← degree[B]-1, degree[B]=2,
swap the positions of B and the first vertex with the same degree as B’s original degree (i.e., swap the position of B and D).
Core Decomposition using Flat Array
The next vertex in the table is E, E’s neighbors are C and F.
For vertex C,
degree[C]>degree[E],
then degree[C] ← degree[C]-1, degree[C]=3, swap the position of C and G.
Core Decomposition using Flat Array
The next vertex in the table is E, E’s neighbors are C and F.
For vertex F,
degree[F]>degree[E],
then degree[F] ← degree[F]-1, degree[F]=4.
Core Decomposition using Flat Array
The next vertex in the table is B, B’s unvisited neighbors are C and D.
For vertex C,
degree[C]>degree[B],
then degree[C] ← degree[C]-1, degree[C]=2. Swap the position of C and D.
Core Decomposition using Flat Array
The next vertex in the table is B, B’s neighbors are C and D.
For neighbor D,
degree[D]>degree[B],
then degree[D] ← degree[D]-1, degree[D]=2. Exchange the position of D and I.
Core Decomposition using Flat Array
The next vertex in the table is C, C’s unvisited neighbors are D and F.
For vertex D, the degree are equal to degree[C] Then the order of table would not change.
degree[F] is updated to 3. Exchange the position of F and G.
Core Decomposition using Flat Array
The next vertex in the table is D, D’s unvisited neighbor is G.
For vertex G,
degree[G]>degree[D],
then degree[G] ← degree[G]-1, degree[G]=3.
Core Decomposition using Flat Array
The next vertex in the table is H, H’s unvisited neighbors are F, G and I.
For vertices F, G and I, degree[F]=degree[G]= degree[H]=degree[I]. Then the order of table would not change.
Core Decomposition using Flat Array
The next vertex in the table is I, I’s unvisited neighbors are F and G.
For vertex F, G,
degree[F]=degree[G]= degree[I].
Then the order of table would not change.
Core Decomposition using Flat Array
The next vertex in the table is F, F’s unvisited neighbor is G
For vertex G, degree[G]=degree[F].
Then the order of table would not change.
Core Decomposition using Flat Array
The next vertex in the table is G, there is no G’s unvisited neighbor.
Core Decomposition using Flat Array
After we traverse all edges in this graph, we get the core number of each vertex in O(m) time.
Core Decomposition using Flat Array
What we need to implement the O(m) algorithm
1. Anarraytosortverticesinnon-decreasingorderofdegree 2. Anarraytolocatethestartpositionforeachdegree
3. Anarraytogetthepositionofeachvertexid
4. Anarraytomaintainthedegreeofeachvertex
tarts at index 7 in D.
graph in Fig. 4 .
b[3] = 7. This is because the block of vertices with degree 2
starts at index 1 in D, and the block of vertices with degree
Table 2: Arrays d, b, D, and p in the BZ algorit graph in Fig. 4 .
Algorithm 4 k-core computation using a flat ar
3 starts at index 7 in D.
updated vertices (left) and max di↵erence from the true coreness (right).
Finally, array p stores for each vertex i its position in D. For instance, vertex 1 is in position 7 in D, thus, p[1] = 7.
An example
Now, the BZ algorithm is given in Algorithm 4.
index d b D p In line 2, arrays d, b, D, and p are initialized. The main
Figure 3: Percentage of updated vertices (left) and max di↵erence from the true coreness (right).
algorithm is in lines 3–17. 1 3 0 5 7 Th
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com