[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Slither: finding local dense subgraphs measured by average degree

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Searching for dense subgraphs is the crux of a variety of graph mining applications. It is also meaningful to investigate problems of finding local dense subgraphs related to particular nodes, especially for large real-world graphs. However, none of the problems focus on maximizing the average degrees of the found subgraphs. We formulate the MDS-N problem, which aims to find such a subgraph with the maximum average degree, near or containing a given node in an undirected graph. We propose the Slither algorithm and the Slither PageRank (PR) algorithm, built on a reduction from the MDS-N problem to the minimum conductance problem and the Lovász-Simonovits Theorem of random walks. A simple hierarchically repetition frame is also proposed to advance the two algorithms. Experiments conducted on both unipartite graphs and bipartite graphs show the effectiveness, stability, and scalability of our algorithms. Additionally, we verify the MDS-N problem and the proposed algorithms on a large social network Twitter, the experimental results of which show our algorithms can successfully detect local fraud-related subgraphs based on particular fraudulent user accounts.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Andersen R (2010) A local algorithm for finding dense subgraphs. ACM Trans Algorithm 6 (4):1–12

    Article  MathSciNet  Google Scholar 

  2. Spielman DA, Teng S-H (2013) A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM J Comput 42(1):1–26

    Article  MathSciNet  Google Scholar 

  3. Andersen R, Chung F, Lang K (2006) Local Graph Partitioning using PageRank Vectors. In: 2006 47Th annual IEEE symposium on foundations of computer science

  4. Tsourakakis CE, Bonchi F, Gionis A, Gullo F, Tsiarli MA (2013) Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 104–112

  5. Hooi B, Song HA, Beutel A, Shah N, Shin K, Faloutsos C (2016) FRAUDAR: Bounding Graph fraud in the face of camouflag. In: International conference on knowledge discovery and data mining, pp 895–904

  6. Kannan R, Vinay V (1999) Analyzing the structure of large graphs, Technical report

  7. Charikar M (2000) Greedy approximation algorithms for finding dense components in a graph. Approximation algorithms for combinatorial optimization, pp 84–95

  8. Abello J, Resende MGC, Sudarsky S (2002) Massive quasi-clique detection. In: Latin american symposium on theoretical informatics, pp 598–612

  9. Uno T (2010) An efficient algorithm for solving pseudo clique enumeration problem. Algorithmica 56(1):3–16

    Article  MathSciNet  Google Scholar 

  10. Zhang S, Zhou D, Yildirim MY, Alcorn S, He J, Davulcu H, Tong H (2017) HiDDen: Hierarchical dense subgraph detection with application to financial fraud detection. In: Proceedings of the 17th SIAM International Conference on Data Mining, pp 570–578

  11. Goldberg AV (1984) Finding a Maximum Density Subgraph. Technical report, University of California, Berkeley

  12. Gallo G, Grigoriadis MD, Tarjan RE (1989) Fast parametric maximum flow algorithm and applications. SIAM J Comput 18(1):30–55

    Article  MathSciNet  Google Scholar 

  13. Håstad J (1999) Clique is hard to approximate within n1−𝜖. Acta Math 182(1):105–142

    Article  MathSciNet  Google Scholar 

  14. Feige U (2004) Approximating maximum clique by removing subgraphs. SIAM J Discret Math 18(2):219–225

    Article  MathSciNet  Google Scholar 

  15. Motzkin TS, Straus EG (1965) Maxima for graphs and a new proof of a theorem of turȧn. Can J Math 17:533–540

    Article  Google Scholar 

  16. Bron C, Kerbosch J (1973) Algorithm 457: finding all cliques of an undirected graph. Commun ACM 16(9):575–577

    Article  Google Scholar 

  17. Seidman SB (1983) Network structure and minimum degree. Soc Netw 5(3):269–287

    Article  MathSciNet  Google Scholar 

  18. Seidman SB, Foster BL (1978) A graph-theoretic generalization of the clique concept. J Math Sociol 6(1):139–154

    Article  MathSciNet  Google Scholar 

  19. Luce RD (1950) Connectivity and generalized cliques in sociometric group structure. Psychometrika 15(2):169–190

    Article  MathSciNet  Google Scholar 

  20. Mokken RJ (1979) Cliques, clubs and clans. Qual Quant 13(2):161–173

    Article  Google Scholar 

  21. Cao Q, Sirivianos M, Yang X, Pregueiro T (2012) Aiding the detection of fake accounts in large scale social online services. In: Proceedings of NSDI 2012: 9th USENIX Symposium on Networked Systems Design and Implementation, pp 197– 210

  22. Jia J, Wang B, Gong NZ (2017) Random walk based fake account detection in online social networks. In: 2017 47Th annual IEEE/IFIP international conference on dependable systems and networks (DSN), pp 273–284

  23. Fogaras D, Rȧcz B (2004) Towards scaling fully personalized pagerank. In: International workshop on algorithms and models for the web-graph, pp 105–117

  24. Lovasz L, Simonovits M (1990) The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume. In: 31St annual symposium on foundations of computer science, pp 346–354

  25. Jindal N, Liu B (2008) Opinion spam and analysis. In: Proceedings of the 2008 international conference on web search and data mining, pp 219–230

  26. Grier C, Thomas K, Paxson V, Zhang M (2010) @Spam The Underground on 140 Characters or Less. In: Proceedings of the 17th ACM conference on Computer and communications security, pp 27–37

  27. Jiang M, Cui P, Beutel A, Faloutsos C, Yang S (2014) Catchsync: catching synchronized behavior in large directed graphs. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 941–950

  28. Yang C, Harkreader R, Zhang J, Shin S, Gu G (2012) Analyzing spammers’ social networks for fun and profit: a case study of cyber criminal ecosystem on twitter. In: Proceedings of the 21st international conference on World Wide Web, pp 71–80

  29. Prakash BA, Seshadri M, Sridharan A, Machiraju S, Faloutsos C (2010) Eigenspokes: Surprising Patterns and Community Structure in Large Graphs. In: Pacific-asia conference on knowledge discovery and data mining, pp 435–448

  30. Shah N, Beutel A, Gallagher B, Faloutsos C (2014) Spotting suspicious link behavior with fbox: an adversarial perspective. In: 2014 IEEE International conference on data mining, pp 959–964

  31. Shin K, Hooi B, Faloutsos C (2016) M-zoom: Fast dense-block detection in tensors with quality guarantees. In: Joint european conference on machine learning and knowledge discovery in databases, pp 264–280

  32. Chung F (2007) Random walks and local cuts in graphs. Linear Algebra Appl 423(1):22–32

    Article  MathSciNet  Google Scholar 

  33. Haveliwala TH (2003) Topic-sensitive pagerank:A context-sensitive ranking algorithm for web search. IEEE Trans Knowl Data Eng 15(4):784–796

    Article  Google Scholar 

  34. Rozemberczki B, Allen C, Sarkar R (2021) Multi-scale Attributed Node Embedding. J Compl Netw 9:(2)

  35. Cho E, Myers SA, Leskovec J (2011) Friendship and mobility: user movement in location-based social networks. In: ACM SIGKDD International conference on knowledge discovery and data mining, pp 1082–1090

  36. Leskovec J, Huttenlocher D, Kleinberg J (2010) Signed networks in social media. In: 28Th ACM conference on human factors in computing systems, pp 1361–1370

  37. McAuley J, Leskovec J (2012) Learning to discover social circles in ego networks. In: Advances in neural information processing systems, vol 1, pp 539–547

  38. McAuley J, Leskovec J (2013) Hidden factors and hidden topics: understanding rating dimensions with review text. In: Proceedings of the 7th ACM conference on Recommender systems, pp 165–172

  39. Tang J, Zhang J, Yao L, Li J, Zhang L, Su Z (2008) Arnetminer: Extraction and mining of academic social networks. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp 990–998

  40. Kwak H, Lee C, Park H, Moon S (2010) What is Twitter, a social network or a news media?. In: Proceedings of the 19th international conference on World Wide Web, pp 591–600

Download references

Acknowledgements

This work is partially supported by Sub Project of Independent Scientific Research Project(No. ZZKY-ZX-03-02-04).

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China

    Zixuan Deng & Yanping Xiang

Authors
  1. Zixuan Deng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yanping Xiang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zixuan Deng.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Deng, Z., Xiang, Y. Slither: finding local dense subgraphs measured by average degree. Appl Intell 52, 5034–5046 (2022). https://doi.org/10.1007/s10489-021-02684-w

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-021-02684-w

Keywords

Search

Navigation