Abstract:
In this work we study the condition number of the least square matrix corresponding to scale free networks. We compute a theoretical lower bound of the condition number which proves that they are ill conditioned. Also, we analyze several matrices from networks generated with Linear Preferential Attachment, Edge Redirection and Attach to Edges models, showing that it is very difficult to compute the power law exponent by the least square method due to the severe lost of accuracy expected from the corresponding condition numbers. © EDP Sciences/Società Italiana di Fisica/Springer-Verlag 2006.
Registro:
Documento: |
Artículo
|
Título: | Condition numbers and scale free graphs |
Autor: | Acosta, G.; Graña, M.; Pinasco, J.P. |
Filiación: | Instituto de Ciencias, Univ. Nac. de Gral. Sarmiento, J.M. Gutierrez 1150, (1613) Los Polvorines, Buenos Aires, Argentina Depto de Matematicas, FCEyN, Ciudad Universitaria, Pab. 1 (1428) Ciudad de Buenos Aires, Argentina
|
Palabras clave: | Least squares approximations; Mathematical models; Matrix algebra; Number theory; Numerical methods; Edges models; Least square methods; Power law exponents; Scale free networks; Graph theory |
Año: | 2006
|
Volumen: | 53
|
Número: | 3
|
Página de inicio: | 381
|
Página de fin: | 385
|
DOI: |
http://dx.doi.org/10.1140/epjb/e2006-00377-4 |
Título revista: | European Physical Journal B
|
Título revista abreviado: | Eur. Phys. J. B
|
ISSN: | 14346028
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14346028_v53_n3_p381_Acosta |
Referencias:
- Golub, G.H., Van Loan, C.F., Matrix computations (1996) Johns Hopkins Series in Mathematical Sciences, 3rd Edn., , The Johns Hopkins University Press, Baltimore and London
- Belsley, D.A., (1991) Conditioning Diagnostics, Collinearity and Weak Data in Regression, , John Wiley & Sons, New York
- Chatterjee, S., Hadi, A.S., Price, B., (1991) Regression Analysis by Example, 3rd Edn., , Wiley Series in Probability and Statistics (John Wiley & Sons)
- Stewart, G.W., (1987) Statistical Science, 2, p. 68
- Achlioptas, D., Clauset, A., Kempe, D., Moore, C., On the bias of traceroute sampling; or, Power-law degree distributions in regular Graphs (2005) Proc. STOC
- Lee, S.H., Kim, P.-J., Jeong, H., (2006) Phys. Rev. E, 73, p. 016102
- Belsley, D.A., Multicollinearity: Diagnosing its presence and assessing the potential damage it causes least squares estimation (1976) National Bureau of Economic Research Working Paper No. 154
- Faloutsos, M., Faloutsos, P., Faloutsos, C., (1999) Computer Commun. Rev., 29, p. 251
- Jeong, H., Tombor, B., Albert, B., Oltvai, Z.N., Barabasi, A.L., (2000) Nature, 407, p. 651
- Newman, M.E.J., (2005) Contemporary Physics, 46, p. 323
- Albert, R., Barabási, A.-L., (2002) Rev. Mod. Phys., 74, p. 47
- Barabási, A.-L., Albert, R., (1999) Science, 286, p. 509
- Krapivsky, P.L., Redner, S., (2001) Phys. Rev. E, 63, p. 066123
- Dorogovtsev, S.N., Mendes, J.F.F., Samukhin, A.N., (2001) Phys. Rev. E, 63, p. 062101
- Khanin, R., Wit, E., (2006) J. Comput. Biology, 13, pp. 810-818
- Handcock, M.S., Jones, J.H., (2003) Nature, 423, p. 605
- Stouffer, D.B., Malmgren, R.D., Amaral, L.A.N., (2005) Nature, 435, p. 207. , arXiv:physics/0510216
- Petermann, T., De Los Rios, P., (2004) Eur. Phys. J. B, 38, p. 201
- Chen, Q., Chang, H., Govindan, R., Jamin, S., Shenker, S.J., Willinger, W., The origin of power laws in internet topologies revisited (2002) Proc. of IEEE Infocom
- Clauset, A., Moore, C., (2005) Phys. Rev. Lett., 94, p. 18701
- Dall'Asta, L., Alvarez-Hamelin, I., Barrat, A., Vazquez, A., Vespignani, A., (2005) Phys. Rev. E, 71, p. 036135
- Lakhina, A., Byers, J., Crovella, M., Xie, P., Sampling biases in IP Topology Measurements (2003) Proc. of IEEE INFOCOM '03
- Goldstein, M.L., Morris, S.A., Yen, G.G., (2004) Eur. Phys. J. B, 41, p. 255
- Krapivsky, P.L., Redner, S., (2002) J. Phys. A, 35, p. 9517
Citas:
---------- APA ----------
Acosta, G., Graña, M. & Pinasco, J.P.
(2006)
. Condition numbers and scale free graphs. European Physical Journal B, 53(3), 381-385.
http://dx.doi.org/10.1140/epjb/e2006-00377-4---------- CHICAGO ----------
Acosta, G., Graña, M., Pinasco, J.P.
"Condition numbers and scale free graphs"
. European Physical Journal B 53, no. 3
(2006) : 381-385.
http://dx.doi.org/10.1140/epjb/e2006-00377-4---------- MLA ----------
Acosta, G., Graña, M., Pinasco, J.P.
"Condition numbers and scale free graphs"
. European Physical Journal B, vol. 53, no. 3, 2006, pp. 381-385.
http://dx.doi.org/10.1140/epjb/e2006-00377-4---------- VANCOUVER ----------
Acosta, G., Graña, M., Pinasco, J.P. Condition numbers and scale free graphs. Eur. Phys. J. B. 2006;53(3):381-385.
http://dx.doi.org/10.1140/epjb/e2006-00377-4