TY - GEN
T1 - On the detectability of node grouping in networks
AU - Wang, Chi
AU - Wang, Hongning
AU - Liu, Jialu
AU - Ji, Ming
AU - Su, Lu
AU - Chen, Yuguo
AU - Han, Jiawei
N1 - Publisher Copyright:
Copyright © SIAM.
PY - 2013
Y1 - 2013
N2 - In typical studies of node grouping detection, the grouping is presumed to have a certain type of correlation with the network structure (e.g., densely connected groups of nodes that are loosely connected in between). People have defined different fitness measures (modularity, conductance, etc.) to quantify such correlation, and group the nodes by optimizing a certain fitness measure. However, a particular grouping with desired semantics, as the target of the detection, is not promised to be detectable by each measure. We study a fundamental problem in the process of node grouping discovery: Given a particular grouping in a network, whether and to what extent it can be discovered with a given fitness measure. We propose two approaches of testing the detectability, namely ranking-based and correlation-based randomization tests. Our methods are evaluated on both synthetic and real datasets, which shows the proposed methods can effectively predict the detectability of groupings of various types, and support explorative process of node grouping discovery.
AB - In typical studies of node grouping detection, the grouping is presumed to have a certain type of correlation with the network structure (e.g., densely connected groups of nodes that are loosely connected in between). People have defined different fitness measures (modularity, conductance, etc.) to quantify such correlation, and group the nodes by optimizing a certain fitness measure. However, a particular grouping with desired semantics, as the target of the detection, is not promised to be detectable by each measure. We study a fundamental problem in the process of node grouping discovery: Given a particular grouping in a network, whether and to what extent it can be discovered with a given fitness measure. We propose two approaches of testing the detectability, namely ranking-based and correlation-based randomization tests. Our methods are evaluated on both synthetic and real datasets, which shows the proposed methods can effectively predict the detectability of groupings of various types, and support explorative process of node grouping discovery.
UR - http://www.scopus.com/inward/record.url?scp=84960124627&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84960124627&partnerID=8YFLogxK
U2 - 10.1137/1.9781611972832.79
DO - 10.1137/1.9781611972832.79
M3 - Conference contribution
AN - SCOPUS:84960124627
T3 - Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013
SP - 713
EP - 721
BT - Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013
A2 - Ghosh, Joydeep
A2 - Obradovic, Zoran
A2 - Dy, Jennifer
A2 - Zhou, Zhi-Hua
A2 - Kamath, Chandrika
A2 - Parthasarathy, Srinivasan
PB - Siam Society
T2 - SIAM International Conference on Data Mining, SDM 2013
Y2 - 2 May 2013 through 4 May 2013
ER -