TY - GEN
T1 - On perturbation theory and an algorithm for maximal clique enumeration in uncertain and noisy graphs
AU - Hendrix, William
AU - Breimyer, Paul
AU - Schmidt, Matthew C.
AU - Samatova, Nagiza F.
PY - 2009
Y1 - 2009
N2 - The maximal clique enumeration (MCE) problem can be used to find very tightly-coupled collections of objects inside a network or graph of relationships. However, when such networks are based on noisy or uncertain data, the solutions to the MCE problem for several closely related graphs may be necessary to accurately define the collections. Thus, we propose an algorithm that efficiently solves the MCE problem on altered, or perturbed, graphs. The algorithm utilizes the enumeration of a baseline graph and identifies only those maximal cliques that the perturbation adds and/or removes. We detail the algorithm and the underlying theory required to guarantee correctness. Further, we report average runtime speedups of 7 and 9 for our algorithm over traditional enumeration techniques in the cases of adding and removing edges, respectively, from graphs constructed from protein interaction data.
AB - The maximal clique enumeration (MCE) problem can be used to find very tightly-coupled collections of objects inside a network or graph of relationships. However, when such networks are based on noisy or uncertain data, the solutions to the MCE problem for several closely related graphs may be necessary to accurately define the collections. Thus, we propose an algorithm that efficiently solves the MCE problem on altered, or perturbed, graphs. The algorithm utilizes the enumeration of a baseline graph and identifies only those maximal cliques that the perturbation adds and/or removes. We detail the algorithm and the underlying theory required to guarantee correctness. Further, we report average runtime speedups of 7 and 9 for our algorithm over traditional enumeration techniques in the cases of adding and removing edges, respectively, from graphs constructed from protein interaction data.
KW - Biological applications
KW - Graph algorithms
KW - Graph perturbation theory
KW - Maximal clique enumeration
UR - http://www.scopus.com/inward/record.url?scp=70450237493&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70450237493&partnerID=8YFLogxK
U2 - 10.1145/1610555.1610562
DO - 10.1145/1610555.1610562
M3 - Conference contribution
AN - SCOPUS:70450237493
SN - 9781605586755
T3 - Proceedings of the 1st ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data, U'09 in Conjunction with KDD'09
SP - 48
EP - 56
BT - Proceedings of the 1st ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data, U'09 in Conjunction with KDD'09
T2 - 1st ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data, U'09 in Conjunction with KDD'09
Y2 - 28 June 2009 through 28 June 2009
ER -