Introduction
-
The edge weight in a co-authorship network may indicate how many papers the two linked authors had co-authored together [10]. Considering the edge weight during community search would ensure that authors within discovered communities have strong co-authoring relationship between them.
-
The edge weight in social network may represent the similarity, or interactions between users [10]. Considering the edge weight in the resulted community would ensure the discovery of highly interacted and similar group of users.
-
Corporate ownership networks (CON), this is a weighted economic network that links 406 different countries, and its weights represent the business ties among countries [11]. Considering the edge weight within the discovered communities would reveal and ensure the business ties between countries.
-
A LOCAL k-TRUSS ALGORITHM (LKA): is proposed as a base solution to apply local search. The algorithm processes edges with the highest weight in sequence. With each edge, the vertices of the edge and their common neighbouring that are processed so far are checked to find out if they form a local k-truss community.
-
A DEGREE-BASED LOCAL k-TRUSS ALGORITHM (DBLKA): based on the fact that any k-truss community must be (k-1)-core community and not vice versa, DBLKA is proposed. Similar to LKA, edges with the highest weight are processed in sequence. With each edge, the vertices of the edge and their common neighbouring that are processed so far are checked to find out if they form a (k-1)-core first before checking if they form a local k-truss community. Consequently, the number of local communities that need to be checked for k-truss existence are decreased which improves search time as shown in "Performance evaluation" section.
-
A MULTIPLE CANDIDATE LOCAL k-TRUSS ALGORITHM (MCLKA): Similar to DBLKA, the algorithm check the existence of (k-1)- core before checking the the existence of local k-truss. On the other hand, the algorithm does the checking process on multiple edges vertices and their common neighbours at once rather than checking each edge case on its own. The collective checking process for multiple candidates has led to a dramatic improvement in terms of search time as shown in "Performance evaluation" section
Related work
Preliminaries
Notation | Description |
---|---|
G = (V, E, W)
| Undirected and edge weighted graph |
n = |V|, m = |E| | Number of vertices and number of edges |
n \(_{X}\)= \(|V_{X}|\), m\(_{X}\) = |E\(_{X}|\) | Number of vertices and number of edges in subgraph X |
nb(v) | The set of neighbors of v |
d(v) | The degree of v |
sup(e,H)
| The support of edge e in subgraph H |
\(\omega ({e})\)
| The weight of edge e |
f(H) | The weight of subgraph H \(\hbox {min}_{{e}\in \hbox {E}_{\mathrm{H}}}\{\omega ({e})\}\) |
S\(_{(u,v)}\) | The common neighbors of vertex (u, v), \(nb(u) \cap nb(v)\) |
\(\tau (H)\)
| The trussness of subgraph H |
E\({_{S}}_{(u,v)}\leftrightarrow {u,v}\) | The set of edges between \({_{S}}_{(u,v)}\) and {u, v} |
-
Connectivity H is a connected subgraph
-
k-truss The minimum sup(e,H) is at least k-2.
-
Maximal There is no other subgraph \(H^\prime\) contains H and the \(f(H^\prime )\)= f(H).
Proposed algorithms
Local k-truss algorithm
-
Build temp graph.
-
Temp graph verification.
-
Enumerating the required top-r weighted k-truss communities.
Degree based local k-Truss Algorithm (DBLKA)
-
Build temp graph.
-
Temp graph verification.
-
Enumerating the required top-r weighted k-truss communities.
Multiple candidates local k-truss algorithm(MCLKA)
-
Generate Multiple Candidates Graph.
-
Multiple Candidates Graph verification.
-
Enumerating the required top-r weighted k-truss communities.
Performance evaluation
Graph | \(|\hbox {V}|\) | \(|\hbox {E}|\) | \(\hbox {k}_{\mathrm{max}}\) |
---|---|---|---|
Wiki-Vote | 8K | 200K | 25 |
Email | 37K | 200K | 20 |
Youtube | 1.1M | 3M | 19 |
Wiki-Talk | 2.4M | 5M | 53 |
Skitter | 1.7M | 11M | 68 |
LiveJournal | 4M | 34.6M | 214 |
Orkut | 3.1M | 117.1M | 78 |