A simple SVD algorithm for finding hidden partitions. (English) Zbl 1386.68110
Summary: Finding a hidden partition in a random environment is a general and important problem which contains as subproblems many important questions, such as finding a hidden clique, finding a hidden colouring, finding a hidden bipartition, etc.
In this paper we provide a simple SVD algorithm for this purpose, addressing a question of McSherry. This algorithm is easy to implement and works for sparse graphs under optimal density assumptions. We also consider an approximating algorithm, which on one hand works under very mild assumptions, but on other hand can sometimes be upgraded to give the exact solution.
In this paper we provide a simple SVD algorithm for this purpose, addressing a question of McSherry. This algorithm is easy to implement and works for sparse graphs under optimal density assumptions. We also consider an approximating algorithm, which on one hand works under very mild assumptions, but on other hand can sometimes be upgraded to give the exact solution.
MSC:
| 68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |
| 68W20 | Randomized algorithms |
| 60C05 | Combinatorial probability |
References:
| [1] | [1]AlonN. and KahaleN. (1997) A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput.261733-1748.10.1137/S0097539794270248 · Zbl 0884.05042 |
| [2] | [2]AlonN., KrivelevichM. and SudakovB. (1998) Finding a large hidden clique in a random graph. Random Struct. Alg.13457-466.10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W · Zbl 0959.05082 |
| [3] | [3]AzarY., FiatA., KarlinA., McSherryF. and SaiaJ. (2001) Spectral analysis of data. In STOC ’1: Proc. 33rd Annual ACM Symposium on Theory of Computing, ACM, pp. 619-626. · Zbl 1323.68426 |
| [4] | [4]BaiZ. and SilversteinJ. W. (2009) Spectral Analysis of Large Dimensional Random Matrices, Springer. · Zbl 1196.60002 |
| [5] | [5]BhatiaR. (1997) Matrix Analysis, Vol. 169 of Graduate Texts in Mathematics, Springer. |
| [6] | [6]BlumA. and SpencerJ. (1995) Coloring random and semi-random k-colorable graphs. J. Algorithms19204-234.10.1006/jagm.1995.1034 · Zbl 0834.05025 |
| [7] | [7]BoppanaR. B. (1987) Eigenvalues and graph bisection: An average-case analysis. In SFCS ’87: Proc. 28th Annual Symposium on Foundations of Computer Science, ACM, pp. 280-285. |
| [8] | [8]BuiT. N., ChaudhuriS., LeightonF. T. and SipserM. (1987) Graph bisection algorithms with good average case behavior. Combinatorica7171-191.10.1007/BF02579448 |
| [9] | [9]ChinP., RaoA. and VuV. (2015) Stochastic block model and community detection in sparse graphs: A spectral algorithm with optimal rate of recovery. Proc. of Machine Learning Research40391-423. |
| [10] | [10]Coja-OghlanA. (2010) Graph partitioning via adaptive spectral techniques. Combin. Probab. Comput.19227-284.10.1017/S0963548309990514 · Zbl 1209.05178 · doi:10.1017/S0963548309990514 |
| [11] | [11]CondonA. and KarpR. M. (2001) Algorithms for graph partitioning on the planted partition model. Random Struct. Alg.18116-140.10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2 · Zbl 0972.68129 |
| [12] | [12]DavisC. and KahanW. M. (1970) The rotation of eigenvectors by a perturbation III. SIAM J. Numer. Anal.71-46.10.1137/0707001 · Zbl 0198.47201 |
| [13] | [13]DekelY., Gurel-GurevichO. and PeresY. (2011) Finding hidden cliques in linear time with high probability. In ANALCO11: Proc. Eighth Workshop on Analytic Algorithmics and Combinatorics, SIAM, pp. 67-75. · Zbl 1290.05129 |
| [14] | [14]DeshpandeY. and MontanariA. (2015) Finding hidden cliques of size <![CDATA \([\sqrt{N/e}]]\)> in nearly linear time. Found. Comput. Math.151069-1128.10.1007/s10208-014-9215-y · Zbl 1347.05227 |
| [15] | [15]DyerM. E. and FriezeA. M. (1986) Fast solution of some random NP-hard problems. In 27th Annual Symposium on Foundations of Computer Science, IEEE, pp. 221-336. |
| [16] | [16]FeigeU. and KrauthgamerR. (2000) Finding and certifying a large hidden clique in a semirandom graph. Random Struct. Alg.16195-208.10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A · Zbl 0940.05050 |
| [17] | [17]FeigeU. and OfekE. (2005) Spectral techniques applied to sparse random graphs. Random Struct. Alg.27251-275.10.1002/rsa.20089 · Zbl 1076.05073 |
| [18] | [18]FeigeU. and RonD. (2010) Finding hidden cliques in linear time. In AofA’10: 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms, DMTCS Proc. AM, pp. 189-204. · Zbl 1355.05186 |
| [19] | [19]FürediZ. and KomlósJ. (1981) The eigenvalues of random symmetric matrices. Combinatorica1233-241.10.1007/BF02579329 · Zbl 0494.15010 |
| [20] | [20]GolubG. H. and Van LoanC. F. (1996) Matrix Computations, Johns Hopkins University Press. · Zbl 0865.65009 |
| [21] | [21]JerrumM. and SorkinG. B. (1993) Simulated annealing for graph bisection. In Proc. 34th Annual IEEE Symposium on Foundations of Computer Science, IEEE, pp. 94-103. FriedmanJ., KahnJ. and SzemerediE. (1989) On the second eigenvalue of random regular graphs, STOC ’89 Proceedings of the twenty-first annual ACM symposium on Theory of computing Pages 587-598. |
| [22] | [22]FriedmanJ., KahnJ. and SzemerédiE. (1989) On the second eigenvalue of random regular graphs. In Proc. of the twenty first annual ACM symposium on theory of computing: STOC, pp. 587-598. |
| [23] | [23]KannanR. and VempalaS. (2009) Spectral Algorithms, Now Publishers Inc. · Zbl 1191.68852 |
| [24] | [24]KučeraL. (1977) Expected behavior of graph coloring algorithms. In Fundamentals of Computation Theory: Proc. 1977 International FCT-Conference, Springer, pp. 447-451. · Zbl 0392.05027 |
| [25] | [25]MatulaD. W. (1972) The employee party problem. Notices Amer. Math. Soc.19A-382. |
| [26] | [26]McDiarmidC. (1998) Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics (M.Habibet al., eds), Springer, pp. 195-248.10.1007/978-3-662-12788-9 · Zbl 0927.60027 |
| [27] | [27]McSherryF. (2001) Spectral partitioning of random graphs. In FOCS 2001: Proc. 42nd IEEE Symposium on Foundations of Computer Science, IEEE, pp. 529-537. |
| [28] | [28]TalagrandM. (1996) A new look at independence. Ann. Probab.241-34.10.1214/aop/1042644705 · Zbl 0858.60019 · doi:10.1214/aop/1042644705 |
| [29] | [29]TurnerJ. (1988) Almost all k-colorable graphs are easy to color. J. Algorithms963-82.10.1016/0196-6774(88)90005-3 · Zbl 0661.68066 · doi:10.1016/0196-6774(88)90005-3 |
| [30] | [30]VuV. (2007) Spectral norm of random matrices. Combinatorica27721-736.10.1007/s00493-007-2190-z · Zbl 1164.05066 · doi:10.1007/s00493-007-2190-z |
| [31] | [31]VuV. and WangK. (2015) Random weighted projections, random quadratic forms and random eigenvectors. Random Struct. Alg.47792-821.10.1002/rsa.20561 · Zbl 1384.60029 |
| [32] | [32]WedinP.-Å. (1972) Perturbation bounds in connection with singular value decomposition. BIT Numer. Math.1299-111.10.1007/BF01932678 · Zbl 0239.15015 · doi:10.1007/BF01932678 |
| [33] | [33]XuR. and WunschD. (2014) Clustering, Wiley. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
