Social Network Analysis PDF

Social Network Analysis CSE505(9) Unit-II Modeling, Aggregating and Knowledge Representation  RDF: Resource Description Framework The Resource Description Framework (RDF) provides a graph-based data model or framework for structuring data as statements ab...

Social Network Analysis CSE505(9) Unit-II Modeling, Aggregating and Knowledge Representation  RDF: Resource Description Framework The Resource Description Framework (RDF) provides a graph-based data model or framework for structuring data as statements about resources A “resource” may be any “thing” that exists in the world: a person, place, event, book, museum object, but also an abstract concept Each statement is composed of a subject, predicate, and object. The subject of a statement is called a resource, the predicate is called a property, and the object is called a value. Each statement is a triple, consisting of these three components. 2  What are Subject, Predicate and Object? In a graph diagram, “nodes” represent things; “edges”(or arc) connect nodes and denote the relationship between them. 3 Example of tabular database DC metadata record for digital image 4 Example of the same metadata in XML URIs: Uniform Resource Identifiers 6 Statements about a digital image  Ontology Term from philosophy co-opted by computer science Definitions  “an explicit and formal specification of a conceptualization”  “defines the concepts and relationships used to describe and represent an area of knowledge” (W3C)  a formal model of the things that exist in a specified knowledge domain and the relationships among those things  "things" may be concepts, works, persons, places, objects, events, etc. Broadest sense: almost any kind of model, schema, or vocabulary; does not have to be encoded More specific Semantic Web sense:  a model encoded in an RDF-based ontology language (e.g., RDFS or OWL)  a computer-actionable model that enables logical inferencing: (e.g., OWL). 8  Ontology A very short and informal way of clarifying what “an ontology” in computing is, is that it is a text file containing structured knowledge about a particular subject domain, and this file is used as a component of a so- called ‘intelligent’ information system. Ontologies have been, and are being, used to solve data integration problems by providing the common, agreed-upon vocabulary which is then used in a way so that the software understands that. For example, an entity Student of a relational database DB1 actually means the same thing as AdvancedLearners in some application software OO2. For instance, a question-answering system that lets the scientist chat with a library chatterbot to more easily find relevant literature (compared to string and keyword matching), automatically find a few theoretically feasible candidate rubber molecules out of very many (compared to painstaking trial-and-error work in the laboratory), and automated discovery of a new enzyme (outperforming the human experts!).  RDF VS OWL 1. Larger Vocabulary: OWL comes with a larger vocabulary and stronger syntax than RDF. For example, OWL includes all your old friends from RDFS such as rdfs:type, rdfs:domain, and rdfs:subPropertyOf. However, OWL also gives you new and better friends! For example, OWL lets you describe you data in terms of set operations: Example:Mother owl:unionOf (Example:Parent, Example:Woman) It lets you define equivalences across databases: AcmeCompany:JohnSmith owl:sameAs PersonalDatabase:JohnQSmith It lets you restrict property values: Example:MyState owl:allValuesFrom (State:NewYork, State:California, …)  RDF VS OWL 2. Logical Consistency: In contrast to RDFS, OWL tells you how you can and cannot use certain vocabulary. In other words, whereas RDFS provides no real constraint mechanisms, OWL does. For example, in RDFS, anything you desire can be an instance of rdfs:Class. You might decide to say that Beagle is an rdfs:Class and then say that Fido is an instance of Beagle: Example: Beagle rdf:Type rdfs:Class Example:Fido rdf:Type Example: Beagle Next, you might decide that you would like to say things about beagles, perhaps you want to say that Beagle is an instance of dogs bred in England: Example:Beagle rdf:Type Example:BreedsBredInEngland Example: BreedsBredInEngland rdf:Type rdfs:Class  RDF VS OWL 3. Constraints and Computability: Unlike RDFS, OWL lets you decide how expressive you want to be, given the computational realities involved. For example, if I know that Example:Frank is of rdf:type Example:Human, and Example:Human is a rdfs:subClassOf Example:Animal, then I can now infer that Example:Frank is also of type Example:Animal. It turns out that some kinds of inferences can be computed quickly. Others can take a REALLY long time to run even on fastest computers. Other kinds of inferences will never be solvable by ANY computer. In fact, OWL allows you to restrict your data modeling options to those that enable faster search queries; those that enable conceptual reasoning; or those that can be easily implemented with rules engines.  RDF VS OWL 4.Annotations, the meta-meta-data: Suppose that you’ve spent the last hour building an ontology that describes your radio manufacturing business. During lunch, your task is to build an ontology for your clock manufacturing business. Next, you’ll have to build an ontology for your highly profitable clock-radio business. Is there a way to easily reuse the morning’s work? OWL makes doing things like this exceedingly easy. Owl:Import is what you would use in the clock-radio situation, but OWL also gives you a rich variety of annotations such as owl:versionInfo, owl:backwardsCompatibleWith, and owl:deprecatedProperty, which can easily be used link data models together into a mutually coherent network of ontologies. Unlike RDFS, OWL is sure to satisfy all of your meta-meta-data- modeling needs.  What does an ontology look like? Example: African Wildlife Ontology (AWO) contains knowledge about wildlife, such as that “all lions eat herbivores, and they also eat some impalas”. A mathematician may prefer to represent such knowledge with first order predicate logic. For instance Ɐx(Lion(x) → Ɐy(eats(x, y) Herbivore(y)) z(eats(x, z) Impala)) One can represent the same knowledge also in logics other than plain vanilla first order logic. For instance, in a Description Logic language, we have the same knowledge formally represented as: Lion Ɐeats.Herbivore eats.Impala A domain expert, however, typically will prefer a more user- friendly rendering, such as an automatically generated (pseudo-)natural language rendering, e.g.: Each lion eats only herbivore and eats some Impala  Graphical Representation Figure : Two graphical rendering of lions eating only herbivores and at least some impala, with the OntoGraf plugin in the Protege 4.x ontology development environment (A) and in UML class diagram style notation (B). Core components of an ontology 16  Class A class is a type of thing. A type of “resource” in the RDF sense: a type of person, place, object, concept, event, etc. Classes and subclasses form a hierarchical taxonomy Members of a subclass inherit the characteristics of their parent class(superclass) Fig: Types of resources specific to a cultural heritage knowledge domain 17  Inheritance Members of a subclass inherit the characteristics and properties of their parent class (superclass) Everything true of the parent class is true also of the child or subclass A member of a subclass “is a”, or “is a kind of” its parent class ClassSubclass relationships must be very strictly logical in RDFS and OWL in order to enable correct computer inferencing. 18  Classes as sets and subsets An alternative way to view classes, subclasses, and inheritance: as sets, represented by Venn style diagrams. 19  Predicates in RDF Ontologies define a set of properties to be used in a specific knowledge domain Properties (predicates) connect or relate resources to each other (subject – predicate --> object) In an ontology context, properties relate members of one class to members of another class, or to a literal Properties convey relationships between resources. In an ontology, they connect members of one class to members of another class (or to a literal)  Domain and Range Restrictions on properties (predicates in RDF triples) Domain restricts what kinds of resources or members of a class can be the subject of a given property in an RDF triple Range restricts what kinds of resources / members of a class or data types (literals) can be the object of a given property in an RDF triple Restrict the possible values (instances) of subjects and object of a given property to members of a specific class or type. 21  Individuals or Instances The specific entities or concepts of interest to us  Concrete specific members or instances of classes For example:  David (by Michelangelo): member of the class Sculpture in a cultural heritage ontology  Maria I. Taylor: member of the class Mother in a family relationships ontology The actual data making up a graph database  Governed by the ontology proper 22 Computer-Supported Collaborative Learning The Ontology proper The RDF triple data structured by the ontology  Knowledge base Machine-readable knowledge bases store knowledge in a computer readable form, usually for the purpose of having automated deductive reasoning applied to them. They contain a set of data, often in the form of rules that describe the knowledge in a logically consistent manner. An ontology can define the structure of stored data - what types of entities are recorded and what their relationships are. Such knowledge bases are also used by the semantic web.  knowledge base A knowledge base is comprised of: An ontology proper Defines the structure of the RDF data, the allowable classes, properties, and their characteristics Individuals: the RDF instance data Statements about the actual things of interest in the knowledge domain (such as specific persons, places, things, events, concepts); must conform to the ontology Inference Inferences expressed as statements  Example for Ontology Model Use Data and information system integration: Integrating legacy systems: Above is a sketch of such a situation about information systems of flower shops, where at the bottom of the figure we have two databases and one application that has been coded in C++. Clearly, the notion of the flower and its colour is the same throughout, even though it is represented differently in the conceptual data models and in the implementations.  Example for Ontology Model Use It is here that the ontology comes into play, for it is the place to assert exactly that underlying, agreed-upon notion. It enables one to assert that: EER’s and UML diagram’s Flower and ORM’s Bloem ‘means’ Flower in the domain ontology, which is indicated with the red dashed arrows. EER’s Colour, ORM’s Kleur and UML’s Color denote the same kind of thing, albeit at one time it is represented as a unary predicate (in ORM) and other times it is a binary relation with a data type, i.e., an attribute. Their ‘mappings’ to the entity in the ontology (green dashed arrows), Colour, indicates that agreement. There is no agreement among the conceptual models when it comes to the data type used in the application, yet they may be mapped into their respective notion in an ontology (purple dashed arrows). For instance, the ColourRegion for the values of the colour(s) in the colour spectrum is a PhysicalRegion, and one might say that the PantoneSystem of colour encoding is an AbstractRegion.  What is knowledge representation? Humans are best at understanding, reasoning, and interpreting knowledge. Human knows things, which is knowledge, and as per their knowledge, they perform various actions in the real world. But how machines do all these things comes under knowledge representation and reasoning(KRR). Hence we can describe Knowledge representation as follows: Knowledge representation and reasoning (KR, KRR) is the part of Artificial intelligence which concerned with AI agents thinking and how thinking contributes to the intelligent behavior of agents. It is responsible for representing information about the real world so that a computer can understand and can utilize this knowledge to solve complex real-world problems such as diagnosis of a medical condition or communicating with humans in natural language. It is also a way that describes how we can represent knowledge in artificial intelligence. Knowledge representation is not just storing data in some database, but it also enables an intelligent machine to learn from that knowledge and experiences so that it can behave intelligently like a human.  What to Represent? Following are the kind of knowledge that needs to be represented in AI systems: Object: All the facts about objects in our world domain. E.g., Guitars contain strings, and trumpets are brass instruments. Events: Events are the actions that occur in our world. Performance: It describes behavior that involves knowledge about how to do things. Meta-knowledge: It is knowledge about what we know. Facts: Facts are the truths about the real world and what we represent. Knowledge-Base: The central component of the knowledge-based agents is the knowledge base. It is represented as KB. A Knowledgebase is a group of Sentences (Here, sentences are used as a technical term and not identical to the English language).  Types of Knowledge 1. Declarative knowledge is to know about something. It includes concepts, facts, and objects. It is also called descriptive knowledge and is expressed in declarative sentences. It is simpler than procedural language. For example, "A car has four tyres." 2. Procedural Knowledge It is also known as imperative knowledge. Procedural knowledge is the type of knowledge that you gain through doing something. For motor tasks, you probably know it as “muscle memory.” It can be directly applied to any task. It includes rules, strategies, procedures, agendas, etc. It depends on the task on which it can be applied.  Types of Knowledge 3. Meta-knowledge: Knowledge about the other types of knowledge is called Meta-knowledge. Meta-Knowledge may be automatically harvested from electronic publication archives, to reveal patterns in research, relationships between researchers and institutions and to identify contradictory results. 4. Heuristic knowledge: Heuristic knowledge is representing the knowledge of some experts in a field or subject. Heuristic knowledge is a hypothesis, common sense, rule of thumb, or intuition based on previous experiences, awareness of approaches, and which are good to work but not guaranteed. Heuristic knowledge helps a person make judgments in a sufficient manner and amount of time. A concrete example of heuristic knowledge would be when a plumber comes to give an estimate to a new customer. AI systems that play chess or Go often employ heuristic knowledge to evaluate board positions and make decisions about their next moves  Types of Knowledge 5. Structural knowledge: Structural knowledge is basic knowledge for problem-solving. It describes relationships between various concepts such as kind of, part of, and grouping of something. It describes the relationship that exists between concepts or objects. Knowledge structures in terms of concepts, sub-concepts and objects. For example, how to various part of car fit together to make a car.  Relation between knowledge and intelligence Knowledge of real-worlds plays a vital role in intelligence and the same for creating artificial intelligence. Knowledge plays an important role in demonstrating intelligent behavior in AI agents. An agent is only able to accurately act on some input when he has some knowledge or experience about that input. Let's suppose if you met some person who is speaking in a language which you don't know, then how you will able to act on that. The same thing applies to the intelligent behavior of the agents. As we can see in the diagram, there is one decision-maker who acts by sensing the environment and using knowledge. But if the knowledge part will not be present then, it cannot display intelligent behavior.  Approaches to knowledge representation 1. Simple relational knowledge: It is the simplest way of storing facts which uses the relational method, and each fact about a set of the object is set out systematically in columns. This approach of knowledge representation is famous in database systems where the relationship between different entities is represented. This approach has little opportunity for inference. Player Weight Age Player1 65 23 Player2 58 18 Player3 75 24 This is the simple relational knowledge representation.  Approaches to knowledge representation 2. Inheritable knowledge: In the inheritable knowledge approach, all data must be stored in a hierarchy of classes. All classes should be arranged in a generalized form or a hierarchal manner. In this approach, we apply inheritance property. Elements inherit values from other members of a class. This approach contains inheritable knowledge which shows a relation between instance and class, and it is called instance relation. Every individual frame can represent the collection of attributes and their value. In this approach, objects and values are represented in Boxed nodes. We use Arrows that point from objects to their values. Approaches to knowledge representation Example for Inheritable knowledge  Approaches to knowledge representation 3. Inferential knowledge: The inferential knowledge approach represents knowledge in the form of formal logic. This approach can be used to derive more facts. It guaranteed correctness. Example: Let's suppose there are two statements: – Marcus is a man – All men are mortal Then it can represent as; man(Marcus) x = man (x) ----------> mortal (x)s  Approaches to knowledge representation 4. Procedural knowledge: The procedural knowledge approach uses small programs and codes which describe how to do specific things, and how to proceed. In this approach, one important rule is used which is the If- Then rule. With In this knowledge, we can use various coding languages such as LISP language and Prolog language. We can easily represent heuristic or domain-specific knowledge using this approach. But it is not necessary that we can represent all cases in this approach.  Requirements for KR system A good knowledge representation system must possess the following properties. 1. Representational Accuracy: KR system should have the ability to represent all kinds of required knowledge. 2. Inferential Adequacy: KR system should have the ability to manipulate the representational structures to produce new knowledge corresponding to the existing structure. 3. Inferential Efficiency: The ability to direct the inferential knowledge mechanism into the most productive directions by storing appropriate guides. 4. Acquisitional efficiency- The ability to acquire new knowledge easily using automatic methods. Techniques of KR  Techniques of KR 1. Logical Representation Logical representation is a language with some concrete rules which deal with propositions and has no ambiguity in representation. Logical representation means drawing a conclusion based on various conditions. This representation lays down some important communication rules. It consists of precisely defined syntax and semantics that support sound inference. Each sentence can be translated into logic using syntax and semantics.  Syntax: Syntaxes are the rules which decide how we can construct legal sentences in the logic. It determines which symbol we can use in knowledge representation. How to write those symbols.  Semantics: Semantics are the rules by which we can interpret the sentence in logic. Semantic also involves assigning a meaning to each sentence.  Techniques of KR Logical representation can be categorized into mainly two logics:  Propositional Logics  Predicate logic Advantages of logical representation:  Logical representation enables us to do logical reasoning.  Logical representation is the basis for programming languages.  Disadvantages of logical Representation:  Logical representations have some restrictions and are challenging to work with.  Logical representation technique may not be very natural, and inference may not be so efficient.  Techniques of KR 2. Semantic Network Representation Semantic networks are alternative to predicate logic for knowledge representation. In Semantic networks, we can represent our knowledge in the form of graphical networks. This network consists of nodes representing objects and arcs which describe the relationship between those objects. Semantic networks can categorize the object in different forms and can also link those objects. Semantic networks are easy to understand and can be easily extended. This representation consists of mainly two types of relations:  IS-A relation (Inheritance)  Kind-of-relation  Techniques of KR Example: Following are some statements that we need to represent in the form of nodes and arcs. Statements:  Jerry is a cat.  Jerry is a mammal  Jerry is owned by Priya.  Jerry is brown colored.  All Mammals are animals.  Techniques of KR Drawbacks in Semantic representation:  Semantic networks take more computational time at runtime as we need to traverse the complete network tree to answer some questions. It might be possible in the worst-case scenario that after traversing the entire tree, we find that the solution does not exist in this network.  Semantic networks try to model human-like memory (Which has 1015 neurons and links) to store the information, but in practice, it is not possible to build such a vast semantic network.  These types of representations are inadequate as they do not have any equivalent quantifier, e.g., for all, for some, none, etc.  Semantic networks do not have any standard definition for the link names.  These networks are not intelligent and depend on the creator of the system. Advantages of Semantic network:  Semantic networks are a natural representation of knowledge.  Semantic networks transparently convey meaning.  These networks are simple and easily understandable.  Techniques of KR 3. Frame Representation A frame is a record-like structure that consists of a collection of attributes and values to describe an entity in the world. Frames are the AI data structure that divides knowledge into substructures by representing stereotypical situations. It consists of a collection of slots and slot values. These slots may be of any type and size. Slots have names and values which are called facets. Facets: The various aspects of a slot are known as Facets. Facets are features of frames that enable us to put constraints on the frames. Example: IF-NEEDED facts are called when data of any particular slot is needed. A-frame may consist of any number of slots, and a slot may include any number of facets and facets may have any number of values. A frame is also known as slot-filter knowledge representation in artificial intelligence.  Techniques of KR Advantages of frame representation: The frame knowledge representation makes the Slots Filters programming easier by grouping the related data. Title Artificial The frame representation is comparably flexible Intelligence and used by many applications in AI. Genre Computer Science It is very easy to add slots for new attributes and Author Peter Norvig relations. It is easy to include default data and to search for Edition Third Edition missing values. Year 1996 Frame representation is easy to understand and Page 1152 visualize. Disadvantages of frame representation: In frame system inference mechanism is not easily processed. Inference mechanism cannot be smoothly proceeded by frame representation. Frame representation has a much more generalized approach.  Techniques of KR 4. Production Rules Production rules system consist of (condition, action) pairs which mean, "If condition then action". It has mainly three parts: The set of production rules Working Memory The recognize-act-cycle Example:  IF (at bus stop AND bus arrives) THEN action (get into the bus)  IF (on the bus AND paid AND empty seat) THEN action (sit down).  IF (on bus AND unpaid) THEN action (pay charges).  IF (bus arrives at destination) THEN action (get down from the bus).  Techniques of KR Advantages of Production rule:  The production rules are expressed in natural language.  The production rules are highly modular, so we can easily remove, add or modify an individual rule. Disadvantages of Production rule:  Production rule system does not exhibit any learning capabilities, as it does not store the result of the problem for future uses.  During the execution of the program, many rules may be active hence rule-based production systems are inefficient. Ontology Based KR Ontology Based KR Types of Ontology Friend Of A Friend (FOAF) Ontology FOAF Ontology Friend Of A Friend (FOAF) Profiles FOAF profiles are created and controlled by the individual user and shared in a distributed fashion. FOAF profiles are typically posted on the personal website of the user and linked from the user’s homepage with the HTML META tag. Distributed nature – FOAF uses the rdfs:seeAlso mechanism to link individual profiles and thus allow the discovery of related profiles. – Address the issues of identification and aggregation with foaf :Person class IFETCE\M.E CSE\III SEM\NE7012-SNA\UNIT 57 2-PPT An FOAF Profile 58 Ontological Representation of Social Individuals Fig: Classes and properties of the FOAF Ontology 59 Ontological Representation of Social Individuals  Benefits and limitations of FOAF Benefits: An advantage of FOAF in terms of sharing FOAF data is the relative stability of the ontology – To facilitate adoption, terms are not added to the vocabulary , rather authors are encouraged to create extensions using the mechanisms of RDF, e.g. creating subclasses and subproperties and adding new properties to existing classes. The terms of the FOAF vocabulary and foaf :Person in particular are also often referenced in other ontologies – SIOC (Semantically Enabled Online Communities) project – DOAP (Description of a Project) ontology. – BuRST format Limitations: FOAF has a poor vocabulary for describing relationships. There is a single foaf :knows relationship defined between Persons and this relationship Use the extensibility of the RDF/OWL language to define more precise notions of relationships. 61  Ontological Representation of Social Relationships Social networks such as FOAF need to be extended to support relationships Support the integration of social information Integrates/aggregates multiple social networks Properties of relationships – Sign: Positive or Negative relationships – Strength (e.g., frequency of contact) – Provenance (different ways of viewing relationships) – Relationship History – Relationship roles Conceptual models for social data – semantic net, RDF 62 Ontological Representation of Social Relationships Ontological Representation of Social Relationships Ontological Representation of Social Relationships Ontological Representation of Social Relationships Aggregating and Reasoning with SN Data Aggregating and Reasoning with SN Data Aggregating and Reasoning with SN Data Aggregating and Reasoning with SN Data Aggregating and Reasoning with SN Data Aggregating and Reasoning with SN Data Aggregating and Reasoning with SN Data Aggregating and Reasoning with SN Data Aggregating and Reasoning with SN Data