Principles of Big Graph: In-depth Insight

Front Cover
Principles of Big Graph: In-depth Insight
Copyright
Contents
Contributors
Preface
Chapter One: CESDAM: Centered subgraph data matrix for large graph representation
1. Introduction
2. Background and related works
2.1. List-based approach
2.1.1. Edge list
2.1.2. Adjacency list and incidence list
2.2. Matrix-based approach
2.2.1. Adjacency matrix
2.2.2. Incidence matrix
2.3. Other related approaches
3. Graph processing and representation
4. Proposed graph representation
4.1. The CESDAM representation scheme
4.2. CESDAM generation
4.2.1. Case 1 edge entry
4.3. CESDAMs from edge list and adjacency matrix
5. Theoretical analysis
5.1. Efficiency of CESDAM representation
5.2. Algorithm complexity
6. Empirical analysis
6.1. Evaluation strategy
6.2. Experimental setup
6.3. Efficiency in terms of memory requirement
6.4. Influence of graph size and density
6.5. Influence of connectivity pattern
7. Conclusion and future work
References
Chapter Two: Bivariate, cluster, and suitability analysis of NoSQL solutions for big graph applications
1. Introduction
2. Outline of study
3. NoSQL for solving big data storage issues
4. Classification criteria for NoSQL solutions
4.1. Big data models
4.1.1. Document-oriented data model
4.1.2. Graph data model
4.1.3. Key-value data model
4.1.4. Wide-column data model
4.2. CAP theorem
4.3. Other features
5. Big graph applications
6. Analysis of NoSQL solutions
6.1. Bivariate analysis
6.2. Clustering analysis
6.2.1. Classification category: Class I
6.2.2. Classification category: Class II
6.2.3. Classification category: Class III
6.2.4. Classification category: Class IV
6.2.5. Classification category: Class V
6.2.6. Classification category: Class VI
7. Suitability study for NoSQL solutions
8. Discussion
9. Conclusion and future work
References
Chapter Three: An empirical investigation on BigGraph using deep learning
1. Introduction
2. Background
3. BigGraph
3.1. Characteristic of BigGraph
3.2. BigGraph frameworks
3.2.1. StellarGraph
3.2.2. PyTorch-BigGraph
3.2.3. Spektral
3.3. Challenges and issues
3.3.1. Graph classification
3.3.2. Node classification
3.3.3. Link prediction
4. Graphs-based deep learning models
4.1. Graph convolutional network
4.2. Deep graph convolutional neural network
4.3. Graph attention networks
4.4. Attributed network embedding via subspace discovery
4.5. GraphSAGE
4.6. Heterogeneous GraphSAGE
4.7. Node2vec
4.8. Metapath2vec
4.9. Continuous-time dynamic network embeddings
4.10. Complex embeddings for simple link prediction
4.11. DistMult
4.12. Relational graph convolutional networks
4.13. Simplifying graph convolutional networks
4.14. Personalized propagation of neural predictions and Approximate personalized propagation of neural predictions
5. Graph-based datasets
5.1. Mutag
5.1.1. Proteins
5.2. DBLP network data
5.3. MovieLens
5.4. Cora
5.5. Blog Catalog 3 dataset
5.6. IAEronEmployees
5.7. WN18
5.8. FB15k
5.9. AIFB dataset
5.10. CiteSeer dataset
5.11. PubMed diabetes dataset
6. Experimental environment setup
7. Experimental results and analysis
8. Conclusion
References
Chapter Four: Analyzing correlation between quality and accuracy of graph clustering
1. Introduction
2. Preliminary definitions
3. Related work
4. Proposed model
5. Validation of proposed model
6. Clustering measures
6.1. Accuracy metrics
6.1.1. ARI
6.1.2. Normalized mutual information (NMI)
6.1.3. Purity
6.1.4. F-measure
6.2. Quality metrics
6.2.1. Modularity
6.2.2. Coverage
6.2.3. External density
7. Empirical analysis
7.1. Experimental setup
7.2. Result analysis
7.3. Analysis with real world network
8. Conclusion
References
Chapter Five: geneBF: Filtering protein-coded gene graph data using Bloom filter
1. Introduction
2. Related works
2.1. Bloom filter
2.2. rDBF
3. geneBF: The proposed system
3.1. Insertion operation
3.2. Query operation
4. Data description
4.1. Key–value dataset
4.2. Protein-coding gene dataset
5. Experimental results and analysis
5.1. Buffer size
5.2. Insertion operation
5.3. Query operation
5.4. False negative and false positive
5.4.1. False negative
5.4.2. False positive
5.5. Operation speed
5.6. Protein-coding gene
6. Discussion
7. Conclusion
References
Chapter Six: Processing large graphs with an alternative representation
1. Introduction
2. The CESDAM representation
3. BFS in adjacency matrix
3.1. Time complexity analysis
3.2. BFT
3.3. Branching factor
4. Graph processing with CESDAM
4.1. Meta-graph preparation
4.1.1. Time complexity analysis
4.2. Meta-breadth-first-search (MBFS)
4.2.1. Time complexity analysis
4.3. Correctness of graph processing
5. Efficiency of CESDAM scheme in terms of space requirement
6. Conclusions
References
Chapter Seven: MapReduce based convolutional graph neural networks: A comprehensive review
1. Introduction
2. Motivation
3. Related work
4. MapReduce and CGNN
4.1. ConVol model
4.1.1. Convolution layer
4.1.2. Pooling layer
4.1.3. Fully connected layer
4.1.4. Activation function
5. Convolutional graph neural network: Evaluation
5.1. MapReduce-based convolutional graph neural networks
5.1.1. Mapper of MapRedGCNN
5.1.2. Reducer of MapRedGCNN
5.1.3. Join of MapRedGCNN
5.2. Benchmarking GCNN through public data sets
6. Applications and challanges of CGNN
6.1. Applications of CGNN
6.1.1. Web recommender systems
6.1.2. Combinatorial optimization
6.1.3. Computer vision
6.2. Pharma-drug discovery
6.3. Challenges of CGNN
6.3.1. Scalability
6.3.2. Dynamic graphs
6.3.3. Complex structures
7. Conclusion
References
Chapter Eight: Fast exact triangle counting in large graphs using SIMD acceleration
1. Introduction
2. Triangle counting algorithm
3. Optimizations
3.1. Exact counting
3.2. Vectorized intersection
4. Evaluation
4.1. Results
5. Applicability
5.1. Truss decomposition
5.2. Frameworks
6. Conclusion
References
Chapter Nine: A comprehensive investigation on attack graphs
1. Introduction
1.1. Necessity of securing a network
1.2. Graph base cyber attack
1.3. Attack graph
1.4. Attack graph models
1.5. Methods for building and analyzing the attack graph
1.6. Scalability of models
1.7. Visualization of the attack graph
1.8. Complexity analysis of various attack graph models
2. Attack graph in security and vulnerability assessment
3. Case study of attack graph
3.1. Case-1: Detection of vulnerabilities in cyber physical system using Attack graph
3.1.1. Pressurized water nuclear power plant(NPP)
3.1.2. Industrial control system (ICS)
3.1.3. Vehicular network system (VNS)
3.2. Case-2: Optimizing IoT devices using attack graph
3.3. Case-3: Risk analysis and security management using Attack graph
4. Conclusion
References
Chapter Ten: Qubit representation of a binary tree and its operations in quantum computation
1. Introduction
2. Related works
3. Representation of a binary tree
4. Operations on quantum binary tree, algorithm, and quantum circuits
4.1. Insertion of a node
4.2. Deletion of node
5. Output measurement, analysis of quantum circuit merits, and complexity
6. Conclusion
References
Chapter Eleven: Modified ML-KNN: Role of similarity measures and nearest neighbor configuration in multi-label text class ...
1. Introduction
2. Methodology
2.1. Problem transformation methods
2.1.1. Binary relevance
2.1.2. Label power set
2.1.3. Classifier chain
2.2. Algorithm adaptation methods
2.2.1. ML-KNN
2.2.2. BPNN
3. Datasets preparation and description
4. Measures used
4.1. Subset accuracy
4.2. Hamming loss
4.3. Example based precision
4.4. Example based recall
4.5. Example based F-measure
4.6. Micro averaged precision
4.7. Micro averaged recall
4.8. Micro averaged F-measure
5. Architecture used for analysis
6. Configuration setup and its requirement
6.1. C0 & C3 configuration
7. Results, graphical representation C0 & C3 and modified ML-KNN algorithm
7.1. C0 configuration
7.2. C3 configuration
7.3. Conventional ML-KNN
7.4. Modified MLKNN
7.5. Algorithm
7.6. Result evaluation based on disease and Seattle dataset
8. Conclusion
9. Future work
Acknowledgments
Conflicting of interests
Funding
References
Chapter Twelve: Big graph based online learning through social networks
1. Introduction
2. Literature review
3. Proposed model
3.1. Concept extraction
3.2. Determining key concept
3.3. Content Recommendation
3.4. Determine relevant content
4. Experimental results
5. Conclusion
References
Chapter Thirteen: Community detection in large-scale real-world networks
1. Introduction
2. Community structure
2.1. Disjoint community
2.2. Overlapping community
2.3. Local community
2.4. Global community
2.5. Static community
2.6. Dynamic community
3. Issues and challenges in detecting communities
3.1. Network size
3.2. Networks dynamic nature
3.3. Overlapping nature of communities
3.4. Scalability
3.5. Estimation of number of communities
3.6. Validation of detected communities
4. Methods for detecting communities
4.1. Local methods
4.2. Global methods
4.2.1. Louvain
4.2.2. FastGreedy
4.2.3. Leading eigenvector
4.2.4. WalkTrap
4.2.5. Label propagation
4.2.6. InfoMap
4.3. Disjoint methods
4.3.1. Divisive hierarchical method
4.3.2. Agglomerative hierarchical methods
4.4. Overlapping methods
4.4.1. CPM
4.4.2. COPRA
4.4.3. OSLOM
4.4.4. SLPA
4.5. Static methods
4.6. Dynamic methods
4.6.1. QCA
4.6.2. BatchInc
4.6.3. GreMod
4.6.4. LBTR
5. Evaluation metrics
5.1. Modularity
5.2. Normalized mutual information
5.3. Adjusted rand index
5.4. F-score
6. Applications
6.1. Epidemic spreading
6.2. Link prediction
6.3. Information diffusion
6.4. Clustering web clients
6.5. Recommendation systems
6.6. Forwarding strategies in communication networks
6.7. Software package refactoring
6.8. Suspicious events detection
6.9. Terrorist group detection
7. Conclusions
References
Chapter Fourteen: Power rank: An interactive web page ranking algorithm
1. Introduction
2. Literature study
3. Proposed methodology
3.1. Description of proposed power rank algorithm
3.2. Power rank algorithm
3.3. Relevancy rule
3.4. Comparative analysis
4. Experimental setup
4.1. Experiment 1
4.2. Experiment 2
5. Conclusion
Acknowledgments
References
Chapter Fifteen: GA-based energy efficient modeling of a wireless sensor network
1. Introduction
2. Motivation
3. Proposed algorithm and structure
3.1. Structure of chromosome
3.2. Fitness function
3.3. Generation of initial population
3.4. Selection
3.5. Crossover
3.6. Mutation
3.7. Removal of population and exit criteria
4. Result analysis
5. Conclusion
References
Chapter Sixteen: The major challenges of big graph and their solutions: A review
1. Introduction
2. Big graph applications
2.1. Biological network
2.2. Social networks
2.3. Wireless ad hoc networks
2.4. The Internet
2.5. The World Wide Web networks
2.6. Semantic networks
2.6.1. Knowledge representation tools
2.6.2. Knowledge graph management systems (KGMS)
2.6.3. Knowledge application services
3. Features of powerful big graph
3.1. Capability of handling flexible data model
3.2. Efficaciousness in managing complex query and analysis
3.3. Scalability
3.4. Permanent storage and transaction support
3.5. Simplicity of use and visualization
4. Big graph issues and challenges
4.1. Graph visualization
4.2. Graph partition and data allocation
4.3. Benchmarking and evaluation
4.4. Dynamic graph analysis
4.5. Data exchange and integration
4.6. Challenges on knowledge graph implementation
4.6.1. Management of entity disambiguation
4.6.2. Resolution of membership type
4.6.3. Knowledge change handling
4.6.4. Knowledge extraction from multiple sources
4.6.5. Managing operations at scale
5. Summary
6. Conclusion
References
Chapter Seventeen: An investigation on socio-cyber crime graph
1. Introduction
2. Online fraud
2.1. Financial crimes
2.2. Cyber terrorism
2.3. E-mail spoofing and phishing scams
2.4. Cyber pornography
3. Types of cyber crimes
3.1. Cyber terrorism
3.2. E-money laundry and tax evasion
3.3. Theft of telecommunications services
3.3.1. Telecommunications piracy
3.4. Fraud in transfer of electronic funds
4. Crimes on the Internet
4.1. Crimes associated with e-mail
4.2. Spoofing of electronic mail
4.2.1. Bombing of e-mail
4.2.2. E-mail defamation
4.2.3. Malicious code spreading
4.2.4. E-mail-sent threats
4.2.5. E-mail frauds
4.3. Who are cyber criminals?
4.3.1. Children
4.3.2. Hacker groups
4.3.3. Employees
4.3.4. Experienced spammers
5. Case studies
5.1. Case I
5.2. Case II
5.3. Case III
5.4. Case IV
6. Experimental evaluation
6.1. Research method
6.2. Procedure
6.3. Applications of cyber crimes theory
6.4. Findings
7. Conclusion
References
Back Cover