research-article

Using an edge-dual graph and k-connectivity to identify strong connections in social networks

Authors:

Brandon DixonAuthors Info & Claims

ACMSE '08: Proceedings of the 46th annual ACM Southeast Conference

Pages 475 - 480

https://doi.org/10.1145/1593105.1593230

Published: 28 March 2008 Publication History

Abstract

How close two entities are in social network is a key factor of SNA (Social Network Analysis). Recent studies of social networks contain a large number of entities and huge number of relations/connections in the networks. Efficiently and accurately analyzing relationships in the network is important component of SNA, especially for law enforcement. In this paper we propose using the edge-dual graph to transform the traditional social network graph to a relation context oriented graph and using modified k-connectivity concepts to evaluate the robustness of the relations. We also describe an implementation of a system based on a 450GB data source, involving 5 million people in Alabama. We use this large scale implementation to evaluate the performance and correctness of the proposal. Our evaluation suggests that using this relation context oriented technology will help to construct a more accurate social network.

References

[1]

Wasserman, S and Faust, K. 1994. Social network analysis: methods and applications. Cambridge University Press. 4--10

[2]

Rheingold, H. 1993. The virtual community: homesteading on the electronic frontier. Addison-Wesley Pub. 1993.

Digital Library

[3]

Said, Y. H., Wegman, E. J., Sharabati, W. K. and Rigsby, J. T. 2008. Social networks of author-coauthor relationships. Computational Statistics & Data Analysis, vol 52 (Jan, 2008), 2177--2184

Digital Library

[4]

Kossinets, G and Watts, D. J. 2006. Empirical Analysis of an Evolving Social Network. Science, vol. 311 (Jan, 2006), 88--90.

[5]

Chen, H., Chung, W., Xu, J. J., Wang, G., Qin, Y., and Chau, M. 2004. Crime data mining: a general framework and some examples. IEEE Computer, vol. 37 (Apr, 2004), 50--56.

Digital Library

[6]

Goldberg, H. G and Wong, R. W. H. 1998. Restructuring databases for knowledge discovery by consolidation and link information. In Proceedings of 1998 AAAI Fall Symposium on Artificial Intelligence and Link Analysis (Menlo Park, CA, 1998).

[7]

Goldberg, H. G and Wong, R. W. H. 1998. Restructuring transactional data for link analysis in the FinCen AI system. In Proceedings of 1998 AAAI Fall Symposium on Artificial Intelligence and Link Analysis (Menlo Park, CA, 1998).

[8]

Hauck, R. V., Atabakhsb, H., Ongvasith, P., Gupta, H., Chen, H. 2002. Using Coplink to analyze criminal-justice data. IEEE Computer, vol. 35 (Mar, 2002), 30--37.

Digital Library

[9]

Xu, J. J., Chen, H. 2004. Fighting organized crimes: using shortest-path algorithms to identify associations in criminal networks. Decision Support Systems, vol. 38 (2004), 473--487.

Digital Library

[10]

Watts, D. J. and Strogatz, S. 1998. Collective dynamics of 'small-world' networks. Nature, vol. 393 (Jun, 1998), 440--442.

[11]

Barabasi, A. L., Jeong, H., Neda, Z., Ravasz, E., Schubert, A. and Vicsek, T. 2002. Evolution of the social network of scientific collaborations. Physica A 311, (3--4) (2002), 590--614.

[12]

Harary, F. 1969. Graph Theory. 45--46

[13]

Moody, J. and White, D. R. 2003. Structural Cohesion and Embeddedness: A Hierarchical Concept of Social Groups. American Sociological Review, vol. 68 (2003), 103--127.

[14]

Clark, J. 1991. A first look at graph theory. World Scientific, 1991.

[15]

Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. 2001. Introduction to algorithms (second edition). MIT Press. 643--662.

Digital Library

[16]

Web site: http://www.jgraph.com/

Cited By

Ding LSteil DDixon BParrish ABrown D(2011)A relation context oriented approach to identify strong ties in social networksKnowledge-Based Systems10.1016/j.knosys.2011.05.00624:8(1187-1195)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1016/j.knosys.2011.05.006
Takahashi DXiao YMeng K(2011)Virtual flow‐net for accountability and forensics of computer and network systemsSecurity and Communication Networks10.1002/sec.4077:12(2509-2526)Online publication date: 27-Dec-2011
https://doi.org/10.1002/sec.407
Takahashi DXiao YMeng K(2010)Notice of Retraction: Creating user-relationship-graph in use of flow-net and log files for computer and network accountability and forensics2010 - MILCOM 2010 MILITARY COMMUNICATIONS CONFERENCE10.1109/MILCOM.2010.5679519(1818-1823)Online publication date: Oct-2010
https://doi.org/10.1109/MILCOM.2010.5679519
Show More Cited By

Index Terms

Using an edge-dual graph and k-connectivity to identify strong connections in social networks

Recommendations

A relation context oriented approach to identify strong ties in social networks

Strong ties play a crucial role in transmitting sensitive information in social networks, especially in the criminal justice domain. However, large social networks containing many entities and relations may also contain a large amount of noisy data. ...
Rainbow trees in graphs and generalized connectivity

An edge-colored tree T is a rainbow tree if no two edges of T are assigned the same color. Let G be a nontrivial connected graph of order n and let k be an integer with 2 ≤ k ≤ n. A k-rainbow coloring of G is an edge coloring of G having the property ...
To Study the Impact of Social Network Analysis on Social Media Marketing Using Graph Theory

Marketing requires an understanding of relationships and current research has progressed much beyond the simple dyadic relationships to look at how social media networks influence the behavior of customers. Social media's power is fascinating as a ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ACMSE '08: Proceedings of the 46th annual ACM Southeast Conference

March 2008

548 pages

ISBN:9781605581057

DOI:10.1145/1593105

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 March 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ACM SE08

ACM SE08: ACM Southeast Regional Conference

March 28 - 29, 2008

Alabama, Auburn

Acceptance Rates

Overall Acceptance Rate 502 of 1,023 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
268
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ding LSteil DDixon BParrish ABrown D(2011)A relation context oriented approach to identify strong ties in social networksKnowledge-Based Systems10.1016/j.knosys.2011.05.00624:8(1187-1195)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1016/j.knosys.2011.05.006
Takahashi DXiao YMeng K(2011)Virtual flow‐net for accountability and forensics of computer and network systemsSecurity and Communication Networks10.1002/sec.4077:12(2509-2526)Online publication date: 27-Dec-2011
https://doi.org/10.1002/sec.407
Takahashi DXiao YMeng K(2010)Notice of Retraction: Creating user-relationship-graph in use of flow-net and log files for computer and network accountability and forensics2010 - MILCOM 2010 MILITARY COMMUNICATIONS CONFERENCE10.1109/MILCOM.2010.5679519(1818-1823)Online publication date: Oct-2010
https://doi.org/10.1109/MILCOM.2010.5679519
Ding LSteil DHudnall MDixon BSmith RBrown DParrish A(2009)PerpSearchProceedings of the 2009 IEEE international conference on Intelligence and security informatics10.5555/1706428.1706456(161-163)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.5555/1706428.1706456
Ding LSteil DHudnall MDixon BSmith RBrown DParrish A(2009)PerpSearch: An integrated crime detection system2009 IEEE International Conference on Intelligence and Security Informatics10.1109/ISI.2009.5137289(161-163)Online publication date: Jun-2009
https://doi.org/10.1109/ISI.2009.5137289

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents