East China Normal University Scientific Reports |
|
v | |
Preface |
|
vii | |
About the Authors |
|
ix | |
Acknowledgments |
|
xi | |
|
1 Introduction to Social Networks |
|
|
1 | (4) |
|
|
1 | (2) |
|
1.2 Challenges of Social Network Mining |
|
|
3 | (1) |
|
|
4 | (1) |
|
|
5 | (18) |
|
2.1 The Types of Networks |
|
|
5 | (6) |
|
|
5 | (3) |
|
|
8 | (1) |
|
|
9 | (2) |
|
|
11 | (5) |
|
|
11 | (1) |
|
|
12 | (1) |
|
|
13 | (1) |
|
2.2.4 Normalized Laplacian Matrix |
|
|
14 | (2) |
|
2.3 Topological Structure |
|
|
16 | (7) |
|
|
16 | (1) |
|
|
17 | (6) |
|
3 R-energy for Evaluating Robustness of Dynamic Networks |
|
|
23 | (26) |
|
|
23 | (2) |
|
|
25 | (2) |
|
|
25 | (1) |
|
|
26 | (1) |
|
|
27 | (4) |
|
3.3.1 2-step Commute Probability |
|
|
27 | (3) |
|
|
30 | (1) |
|
3.4 Computation of R-energy |
|
|
31 | (4) |
|
|
31 | (2) |
|
|
33 | (2) |
|
3.5 Robustness of Large Static Networks |
|
|
35 | (5) |
|
3.5.1 Experimental Network |
|
|
35 | (2) |
|
3.5.2 Efficiency and Scalability of R-energy |
|
|
37 | (1) |
|
3.5.3 Impact of Vertex Removal to R-energy |
|
|
38 | (2) |
|
3.6 Detecting Events and Trends Using Robustness |
|
|
40 | (7) |
|
|
40 | (1) |
|
|
41 | (3) |
|
3.6.3 Periodic Trend Pattern Detection |
|
|
44 | (3) |
|
|
47 | (2) |
|
4 Network Linkage Across Heterogeneous Networks |
|
|
49 | (30) |
|
|
49 | (2) |
|
|
50 | (1) |
|
4.1.2 Objectives and Contributions |
|
|
50 | (1) |
|
|
51 | (2) |
|
4.2.1 Network Linkage Across Social Platforms |
|
|
51 | (2) |
|
|
53 | (1) |
|
|
53 | (1) |
|
|
54 | (4) |
|
|
54 | (3) |
|
|
57 | (1) |
|
|
58 | (10) |
|
4.5.1 User Attribute and Social Similarity |
|
|
58 | (4) |
|
4.5.2 Parameter Learning and Matching Score Computation |
|
|
62 | (4) |
|
|
66 | (2) |
|
|
68 | (10) |
|
4.6.1 Dataset and Settings |
|
|
68 | (2) |
|
4.6.2 User Self-linkage Evaluation |
|
|
70 | (4) |
|
4.6.3 Heterogeneous User Linkage Evaluation |
|
|
74 | (4) |
|
|
78 | (1) |
|
5 Quasi-biclique Detection from Bipartite Graphs |
|
|
79 | (34) |
|
|
79 | (1) |
|
|
80 | (2) |
|
|
82 | (5) |
|
|
82 | (3) |
|
|
85 | (2) |
|
|
87 | (12) |
|
5.4.1 Input Graph Pruning |
|
|
87 | (1) |
|
5.4.2 Induced Graph Pruning |
|
|
88 | (8) |
|
5.4.3 Combined Pruning Rules for an Induced Graph |
|
|
96 | (2) |
|
5.4.4 Complexity Analysis |
|
|
98 | (1) |
|
5.5 Enumeration of Maximal Quasi-biclique Communities |
|
|
99 | (6) |
|
|
99 | (2) |
|
5.5.2 Enumerating Vertex Set |
|
|
101 | (1) |
|
5.5.3 Enumerating all QBCs of a Candidate Graph |
|
|
102 | (2) |
|
|
104 | (1) |
|
5.5.5 Complexity Analysis |
|
|
105 | (1) |
|
|
105 | (2) |
|
5.6.1 Outline of the Algorithm |
|
|
106 | (1) |
|
|
107 | (5) |
|
5.7.1 Datasets and Settings |
|
|
107 | (1) |
|
5.7.2 Performance Results of MQBCD |
|
|
108 | (2) |
|
5.7.3 Comparison with Baseline |
|
|
110 | (1) |
|
|
111 | (1) |
|
|
112 | (1) |
|
6 On Detecting Antagonistic Community Detection from Signed Graphs |
|
|
113 | (52) |
|
|
113 | (6) |
|
|
113 | (4) |
|
6.1.2 Research Objectives |
|
|
117 | (2) |
|
|
119 | (1) |
|
|
120 | (3) |
|
|
120 | (2) |
|
|
122 | (1) |
|
|
123 | (10) |
|
6.4.1 Input Graph Pruning |
|
|
124 | (1) |
|
6.4.2 Induced Graph Pruning |
|
|
125 | (5) |
|
6.4.3 Combined Pruning Rules for an Induced Graph |
|
|
130 | (2) |
|
6.4.4 Complexity Analysis |
|
|
132 | (1) |
|
|
133 | (5) |
|
|
133 | (2) |
|
6.5.2 Enumerating All QACs of a Candidate Graph |
|
|
135 | (2) |
|
|
137 | (1) |
|
6.5.4 Complexity Analysis |
|
|
138 | (1) |
|
|
138 | (4) |
|
6.6.1 Outline of Algorithm |
|
|
138 | (3) |
|
|
141 | (1) |
|
6.7 Experiments on Synthetic Graph |
|
|
142 | (12) |
|
|
142 | (4) |
|
6.7.2 Performance Results |
|
|
146 | (8) |
|
6.8 Experiments on Real Networks |
|
|
154 | (8) |
|
6.8.1 Description of Datasets |
|
|
154 | (1) |
|
6.8.2 Performance Results |
|
|
155 | (4) |
|
|
159 | (1) |
|
6.8.4 Predicting Polarity of Links |
|
|
160 | (2) |
|
6.8.5 Discussion: Coverage and Applicability |
|
|
162 | (1) |
|
|
162 | (3) |
|
|
165 | (4) |
|
|
165 | (1) |
|
7.2 Discussion of Future Directions |
|
|
166 | (3) |
Bibliography |
|
169 | (8) |
Index |
|
177 | |