Weitere Artikel dieser Ausgabe durch Wischen aufrufen
This material is based upon work supported by the Air Force Office of Scientific Research, Asian Office of Aerospace Research and Development (AOARD) under award number FA2386-16-1-4032, and JSPS Grant-in-Aid for Scientific Research (C) (No. 17K00314).
We address the problem of efficiently detecting critical links in a large network. Critical links are such links that their deletion exerts substantial effects on the network performance such as the average node reachability. We tackle this problem by proposing a new method which consists of three acceleration techniques: redundant-link skipping (RLS), marginal-node pruning (MNP) and burn-out following (BOF). All of them are designed to avoid unnecessary computation and work both in combination and in isolation. We tested the effectiveness of the proposed method using two real-world large networks and two synthetic large networks. In particular, we showed that the proposed method can estimate the performance degradation by link removal without introducing any approximation within a computation time comparable to that needed by the bottom-k sketch which is a summary of dataset and can efficiently process approximate queries, i.e., reachable nodes, on the original dataset, i.e., the given network. Further, we confirmed that the measures easily composed by the well known existing centralities, e.g. in/out-degree, betweenness, PageRank, authority/hub, are not able to detect critical links. Links detected by these measures do not reduce the average reachability at all, i.e., not critical at all.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Albert, R., Jeong, H., Barabási, A.L. (2000). Error and attack tolerance of complex networks. Nature, 406, 378–382. CrossRef
Boldi, P., & Vigna, S. (2013). In-core computation of geometric centralities with hyperball: a hunderd billion nodes and beyond. In Proceedings of the 2013 IEEE 13th international conference on data mining workshops (ICDMW’13) (pp. 621–628).
Bonchi, F., Castillo, C., Ienco, D. (2013). Meme ranking to maximize posts virality in microblogging platforms. Journal of Intelligent Information Systems, 40, 211–239. CrossRef
Borgs, C., Brautbar, M., Chayes, J., Lucier, B. (2014). Maximizing social influence in nearly optimal time. In Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms (SODA’14) (pp. 946–957).
Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 30, 107–117. CrossRef
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J. (2000). Graph structure in the web. In Proceedings of the 9th international world wide web conference (pp. 309–320).
Callaway, D.S., Newman, M.E.J., Strogatz, S.H., Watts, D.J. (2000). Network robustness and fragility: percolation on random graphs. Physical Reveiw Letters, 85, 5468–5471. CrossRef
Chakrabarti, S., Dom, B., Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A., Gibson, D., Kleinberg, J. (1999). Mining the web’s link structure. IEEE Computer, 32, 60–67. CrossRef
Chen, W., Lakshmanan, L., Castillo, C. (2013). Information and influence propagation in social networks. Synthesis Lectures on Data Management, 5(4), 1–177. CrossRef
Chierichetti, F., Epasto, A., Kumar, R., Lattanzi, S., Mirrokni, V. (2015). Efficient algorithms for public-private social networks. In Proceedings of the 21st ACM SIGKDD international conference on knowledge discovery and data mining (KDD’15) (pp. 139–148).
Cohen, E., Delling, D., Pajor, T., Werneck, R.F. (2014). Sketch-based influence maximization and computation: scaling up with guarantees. In Proceedings of the 23rd ACM international conference on conference on information and knowledge management (pp. 629–638).
Freeman, L. (1979). Centrality in social networks: conceptual clarification. Social Networks, 1, 215– 239. CrossRef
Kempe, D., Kleinberg, J., Tardos, E. (2003). Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining (KDD’03) (pp. 137–146).
Kimura, M., Saito, K., Motoda, H. (2009). Blocking links to minimize contamination spread in a social network. ACM Transactions on Knowledge Discovery from Data, 3, 9:1–9:23. CrossRef
Kimura, M., Saito, K., Nakano, R. (2007). Extracting influential nodes for information diffusion on a social network. In Proceedings of the 22nd AAAI conference on artificial intelligence (AAAI-07) (pp. 1371–1376).
Kimura, M., Saito, K., Ohara, K., Motoda, H. (2014). Efficient analysis of node influence based on sir model over huge complex networks. In Proceedings of the 2014 international conference on data science and advanced analytics (DSAA’14) (pp. 216–222).
Kimura, M., Saito, K., Ohara, K., Motoda, H. (2016). Speeding-up node influence computation for huge social networks. International Journal of Data Science and Analytics, 1, 1–14. CrossRef
Newman, M.E.J., Forrest, S., Balthrop, J. (2002). Email networks and the spread of computer viruses. Physical Review E, 66(035), 101.
Ohara, K., Saito, K., Kimura, M., Motoda, H. (2014). Resampling-based framework for estimating node centrality of large social network. In Proceedings of the 17th international conference on discovery science (DS’14) (pp. 228–239). LNAI 8777.
Saito, K., Kimura, M., Ohara, K., Motoda, H. (2016). Detecting critical links in complex network to maintain information flow/reachability. In Proceedings of the 14th Pacific Rim international conference on artificial intelligence (pp. 419–432).
Saito, K., Ohara, K., Kimura, M., Motoda, H. (2017). An accurate and efficient method to detect critical links to maintain information flow in network. In Proceedings of the 23th international symposium on methodologies for intelligent systems (pp. 116–126).
Song, G., Zhou, X., Wang, Y., Xie, K. (2015). Influence maximization on large-scale mobile social network: a divide-and-conquer method. IEEE Transactions on Parallel and Distributed Systems, 26, 1379–1392. CrossRef
Thapa, M., Espejo-Uribe, J., Pournaras, E. (2017). Measuring network reliability and repairability against cascading failures. Journal of Intelligent Information Systems. https://doi.org/10.1007/s10844-017-0477-0. Online First.
Zhou, C., Zhang, P., Zang, W., Guo, L. (2015). On the upper bounds of spread for greedy algorithms in social network influence maximization. IEEE Transactions on Knowledge and Data Engineering, 27, 2770–2783. CrossRef
- Accurate and efficient detection of critical links in network to minimize information loss
- Springer US
Neuer Inhalt/© ITandMEDIA, Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung/© astrosystem | stock.adobe.com