, we have N 1 (z) ? b?N k?2 (x) N 1 (b) By definition, N 1 (z) = K(O k?3 (z) and b?N k?2 (x) N 1 (b) = K(O k?2 (x)). We then obtain K(O k?3 (z)) ? K(O k?2 (x)), which gives, pp.3-5
, Again, since z ? W k?2 (x), we have O k?3 (x) ? O k?3 (z) ? O k?2 (x) Since we already proved that N k?1 (x) = W k?1 (x), O k?4 (x)), and then, pp.3-3
, |N k?2 (x)| > 1, necessarily O k?3 (x) O k?2 (x) Similarly, the fact that N k?1 (x) = W k?1 (x) and |N k?1 (x)| > 1 implies that O k?2 (x) O k?1 (x) At last, from Remark 3, we have K(O k?1 (x)) = N 1 (x), and since |N 1 (x)| ? 2, it follows that |K(O k?1 (x))| ? 2. Combined with the fact that |O 1 (x)| ? 2
, From recursion hypothesis H sur (k ? 1), for any P ? O such that O k?3 P , there exists y P ? V k?1 such that S(y P ) = (O 1 , We denote by Y the set = (O 1 , . . . , O k?3 ) and O k?2 ? V * k and is therefore an element of V k . In order to conclude the proof of H sur (k), let us now show that the element x of V k has the desired characterising sequence (O 1 , . . . , O k?1 ). First, from H N (k), which we already proved, we know that O k?3 ), from the definition of x = Y y?Y N (y). Second, from Remark 3, we have K(O k?1 (x)) = N 1 (x) and we already know that |N 1 (x)| ? 2 (see beginning of the proof of H sur (k)), k?1 ) ? O k?1 such that O 1 . . . O k?1 O k?3 (y)) for any y ? N k?1 (x), which gives (O 1 (x), . . . , O k?3 (x)) = (O 1 This gives |K(O k?1 (x))| ? 2, and as we have |O 1 (x)| ? 2 and O 1 (x) ? . . . ? O k?2 (x) ? O k?1 (x), we obtain that O k?2 (x), O k?1 (x) ? O. Now, from H N (k), we know that the couple (O k?2 (x), O k?1 (x)) is such that N k?1 (x) = {y ? V k?1 | O k?2
, Statistical mechanics of complex networks, Reviews of Modern Physics, vol.74, issue.1, p.47, 2002.
DOI : 10.1103/RevModPhys.74.47
, Consensus algorithms for the generation of all maximal bicliques, Discrete Applied Mathematics, vol.145, issue.1, pp.11-21, 2004.
DOI : 10.1016/j.dam.2003.09.004
, Ccnr network databases, 2007.
, Dynamical processes on complex networks, 2010.
DOI : 10.1017/CBO9780511791383
, The asymptotic number of labeled graphs with given degree sequences, Journal of Combinatorial Theory, Series A, vol.24, issue.3, pp.296-307, 1978.
DOI : 10.1016/0097-3165(78)90059-6
, On clique convergent graphs, Graphs and Combinatorics, vol.103, issue.3, pp.213-220, 1995.
DOI : 10.1007/BF01793007
, Clique Graphs and Edge-clique graphs, Electronic Notes in Discrete Mathematics, vol.13, pp.34-37, 2003.
DOI : 10.1016/S1571-0653(04)00432-9
, Edge-clique graphs, Graphs and Combinatorics, vol.10, issue.3, pp.253-264, 1991.
DOI : 10.1007/BF01787631
, Clique graphs and overlapping communities, Journal of Statistical Mechanics: Theory and Experiment, vol.2010, issue.12, p.12037, 2010.
DOI : 10.1088/1742-5468/2010/12/P12037
, Enumeration aspects of maximal cliques and bicliques, Discrete Applied Mathematics, vol.157, issue.7, pp.1447-1459, 2009.
DOI : 10.1016/j.dam.2008.10.010
, The number of convergent graphs under the biclique operator with no twin vertices is finite, Electronic Notes in Discrete Mathematics, vol.35, pp.241-246, 2009.
DOI : 10.1016/j.endm.2009.11.040
, On the Iterated Biclique Operator, Journal of Graph Theory, vol.33, issue.1-3, pp.181-190, 2013.
DOI : 10.1002/jgt.21666
, Bipartite structure of all complex networks, Information Processing Letters, vol.90, issue.5, pp.215-221, 2004.
DOI : 10.1016/j.ipl.2004.03.007
URL : https://hal.archives-ouvertes.fr/hal-00016855
, Bipartite graphs as models of complex networks, Physica A: Statistical Mechanics and its Applications, vol.371, issue.2, pp.795-813, 2006.
DOI : 10.1016/j.physa.2006.04.047
, The clique operator on cographs and serial graphs, Discrete Mathematics, vol.282, issue.1-3, pp.183-191, 2004.
DOI : 10.1016/j.disc.2003.10.023
, Clique divergent clockwork graphs and partial orders, Discrete Applied Mathematics, vol.141, issue.1-3, pp.195-207, 2004.
DOI : 10.1016/S0166-218X(03)00378-0
, Contractibility and the clique graph operator, Discrete Mathematics, vol.308, issue.16, pp.3461-3469, 2008.
DOI : 10.1016/j.disc.2007.07.004
, Termination of Multipartite Graph Series Arising from Complex Network Modelling, 4th International Conference on Combinatorial Optimization and Applications -COCOA'10, pp.1-10, 2010.
DOI : 10.1007/978-3-642-17458-2_1
URL : https://hal.archives-ouvertes.fr/hal-00644239
, The clique operator on circular-arc graphs, Discrete Applied Mathematics, vol.158, issue.12, pp.1259-1267, 2010.
DOI : 10.1016/j.dam.2009.01.019
, A critical point for random graphs with a given degree sequence. Random Structures and Algorithms, 1995.
, On clique-divergent graphs, Probì emes Combin. Théorie Graphes (Colloques internationaux du C, pp.313-315, 1978.
, Termination of the iterated strong-factor operator on multipartite graphs, 2013.
URL : https://hal.archives-ouvertes.fr/hal-01241925
, Convergence of iterated clique graphs, Discrete Mathematics, vol.103, issue.2, pp.199-207, 1992.
DOI : 10.1016/0012-365X(92)90270-P
, A Survey on Clique Graphs, Recent Advances in Algorithms and Combinatorics, pp.109-136, 2003.
DOI : 10.1007/0-387-22444-0_5
, The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, vol.363, issue.1, pp.28-42, 2006.
DOI : 10.1016/j.tcs.2006.06.015
, Lcm program (linear time closed itemset miner) Http
, An Efficient Algorithm for Enumerating Closed Patterns in Transaction Databases, 7th International Conference, pp.16-31, 2004.
DOI : 10.1007/978-3-540-30214-8_2
, A New Algorithm for Enumerating All Maximal Cliques in Complex Network, Advanced Data Mining and Applications, Second International Conference -ADMA'06, pp.606-617, 2006.
DOI : 10.1007/11811305_67
, Collective dynamics of small-world networks, Nature, vol.393, issue.6684, pp.440-442, 1998.
DOI : 10.1038/30918